Note: This article is available in Chinese only. 本文暂无英文版本。
View original
思路：一个老式的电话键盘。。。。给出一个拨号的移动路径。。。问这个路径是否唯一。
思路：如果唯一就说明。。。不能平移。。。否则不唯一。。
平移可以上下左右。。所以先写4个常亮数组。。。标记平移后的结果。。。设置不合法位就可以了。。。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月18日 星期一 12时56分28秒
4File Name :code/2016whust/E.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33
34const int up[15]={8,-1,-1,-1,1,2,3,4,5,6};
35const int down[15]={-1,4,5,6,7,8,9,-1,0,-1};
36const int l[15]={-1,-1,1,2,-1,4,5,-1,7,8};
37const int r[15]={-1,2,3,-1,5,6,-1,8,9,-1};
38int n;
39string st;
40
41bool solve()
42{
43 bool flag = true;
44 for ( int i = 0 ; i < n ; i++)
45 {
46 int x = st[i]-'0';
47// cout<<"x:"<<x<<" x+up[x]"<<x+up[x]<<endl;
48 x = up[x];
49 if (x==-1)
50 {
51 flag = false;
52// cout<<"uuuuu"<<endl;
53 break;
54 }
55 }
56 if (flag) return true;
57
58 flag = true;
59 for ( int i = 0 ; i < n ; i++)
60 {
61 int x = st[i]-'0';
62 x = down[x];
63 if (x==-1)
64 {
65 flag = false;
66// cout<<"ddd"<<endl;
67 break;
68 }
69 }
70 if (flag) return true;
71
72 flag = true;
73 for ( int i = 0 ; i < n; i++)
74 {
75 int x = st[i]-'0';
76 x = l[x];
77 if (x==-1)
78 {
79 flag = false;
80// cout<<"lll"<<endl;
81 break;
82 }
83 }
84
85 if (flag) return true;
86 flag = true;
87
88 for ( int i = 0 ; i < n ; i++)
89 {
90 int x = st[i]-'0';
91 x = r[x];
92 if (x==-1)
93 {
94 flag = false;
95// cout<<"rrr:::"<<endl;
96 break;
97 }
98 }
99 if (flag) return true;
100
101 return false;
102
103
104}
105int main()
106{
107 #ifndef ONLINE_JUDGE
108 freopen("code/in.txt","r",stdin);
109 #endif
110
111
112 cin>>n;
113 cin>>st;
114 if (!solve())
115 {
116 puts("YES");
117 }
118 else
119 {
120 puts("NO");
121 }
122
123
124
125 #ifndef ONLINE_JUDGE
126 fclose(stdin);
127 #endif
128 return 0;
129}