题目意思是有个人的手机掉水里了,他打电话只能靠平时拨号的按键习惯来拨号。请问他按下一串号码后会不会出现重复的情况。

        模拟一下就好了,我们可以把他按按键的顺序看成是走迷宫的顺序,记录下来,然后从0-9挨个开始按照这种走迷宫的方式走,如果超出边界了就返回,如果找到相同路径就计数++,计数超过1个我们就可以输出NO,只有一个情况那就输出YES。


题目:http://codeforces.com/problemset/problem/689/A


代码:

Memory: 2044 KB
Time: 15 MS
Language: GNU G++ 4.9.2
Result: Accepted
#include <iostream>
#include <cstdio>
#include <cstring>
#include <memory.h>
#include <queue>
using namespace std;
char num[10];
int omap[6][6];
int go[10][2];
int cnt=0;
int x;
struct Point{
    int x, y;
}myqueue[10];
void Init()
{
    memset(omap, -1, sizeof(omap));
    int add=1;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            {
                go[add][0]=i;
                go[add][1]=j;
                omap[i][j]=add++;
            }
    omap[4][2]=0;
    go[0][0]=4;
    go[0][1]=2;
}
bool dfs(int q)
{
    for(int i=0;i<cnt;i++)
    {
        int dx=go[q][0]+myqueue[i].x;
        int dy=go[q][1]+myqueue[i].y;
        if(dx>4 || dx<1 || dy>3 || dy<1 || omap[dx][dy]==-1)return 0;
        q=omap[dx][dy];
    }
    return 1;
}
bool Process()
{
    int t1, t2;
    t1=num[0]-'0';
    cnt=0;
    for(int i=1;i<x;i++)
    {
        t2=num[i]-'0';
        Point temp;
        temp.x=go[t2][0]-go[t1][0];
        temp.y=go[t2][1]-go[t1][1];
        myqueue[cnt++]=temp;
        t1=t2;
    }
    int tcnt=0;
    for(int i=0;i<10;i++)
    {
        if(dfs(i))tcnt++;
    }
    if(tcnt==1)return 1;
    else return 0;
}
int main()
{
    Init();
    while(cin>>x)
    {
        scanf("%s", &num);
        if(x==1)printf("NO\n");
        else
        {
            if(Process())printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}