2018/7/31-zznu-oj-问题 F: 手机密码--【裸dfs+for循环即可！——据说三个小时内只有两个人读完了题意并轻松AC了】

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

问题 F: 手机密码

时间限制: 1 Sec 内存限制: 128 MB
提交: 41 解决: 23
[提交] [状态] [讨论版] [命题人:admin]

题目描述手机安全问题是大家经常关心的一个问题。
在生物解锁没有出现之前，人们通常有两种方式设置手机密码：九宫格密码和数字密码。
我们先来简化一下这两种密码的格式：
对于九宫格密码：
.至少连接4个以上不同的圆点。
.只能连接相邻（八方向）的圆点，且每个圆点只能通过一次。
.密码的长度定义为经过的圆点数。
对于数字密码：
.至少含有四个数字。
.密码长度定义为字符数。
现在，我们来尝试用枚举来破解这两种密码，当然我们可以提前获知一些消息：
.你可以通过观察对方解锁手机所用的时长，大致推断出对方的密码长度，
.在通常情况下，我们可以很轻松的得到密码第一位的信息，因为它最常被触碰比较油腻。而后，你来计算一下，对于这两种密码，最差我们需要枚举多少次，才能解开这组密码。输入出入包含四个整数n,a,x,y，
正整数n代表密码长度，
整数a代表数字密码的一位，
正整数(x,y)，代表九宫格密码第一个经过的圆点的坐标
输入已EOF结束输出输出包含两个正整数，分别代表最差尝试几次可以破解九宫格密码，和数字密码样例输入样例输出提示九宫格密码的左上角坐标为（，）

思路：

有点长的题目，裸DFS，暴力一遍OK！

题解代码：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<string>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
#define N 10000
#define ll long long
int mp[][];//(1,1)--(3,3)
int ans1;
int dir[][]={ {,},{,},{,-},{-,},{,-},
{,},{-,},{-,-} };
int vis[][];
int n;
void dfs(int x,int y,int step){
if(step==n)
{
ans1++;return ;
}
for(int i=;i<=;i++){
int dx,dy;
dx=x+dir[i][];
dy=y+dir[i][];
if(dx>=&&dy>=&&dx<=&&dy<=&&!vis[dx][dy]){
vis[dx][dy]=;
dfs(dx,dy,step+);
vis[dx][dy]=;
}
} }
int main()
{
int beg,x,y;
while(scanf("%d%d%d%d",&n,&beg,&x,&y)!=EOF){
ans1=;
ll ans2=;
memset(vis,,sizeof(vis)); vis[x][y]=;
dfs(x,y,); for(int i=;i<=n;i++)
ans2*=; printf("%d %lld\n",ans1,ans2);
} return ;
}