写一半去开程序的时候不小心关了网页,LOFTER我都不奢望加入代码高亮,最起码我关闭的时候弹个对话框,再不济也给我定时保存一下草稿吧。
A. Mike and Cellphone
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
While swimming at the beach, Mike has accidentally dropped his cellphone into the water. There was no worry as he bought a cheap replacement phone with an old-fashioned keyboard. The keyboard has only ten digital equal-sized keys, located in the following way:
Together with his old phone, he lost all his contacts and now he can only remember the way his fingers moved when he put some number in. One can formally consider finger movements as a sequence of vectors connecting centers of keys pressed consecutively to put in a number. For example, the finger movements for number "586" are the same as finger movements for number "253":
Mike has already put in a number by his "finger memory" and started calling it, so he is now worrying, can he be sure that he is calling the correct number? In other words, is there any other number, that has the same finger movements?
Input
The first line of the input contains the only integer n (1 ≤ n ≤ 9) — the number of digits in the phone number that Mike put in.
The second line contains the string consisting of n digits (characters from '0' to '9') representing the number that Mike put in.
Output
If there is no other phone number with the same finger movements and Mike can be sure he is calling the correct number, print "YES" (without quotes) in the only line.
Otherwise print "NO" (without quotes) in the first line.
Examples
input
3 586
output
NO
input
2 09
output
NO
input
9 123456789
output
YES
input
3 911
output
YES
Note
You can find the picture clarifying the first sample case in the statement above.
·
题意: 对于给定手机键盘上这n个数,手势是否唯一确定这一个数?是的话输出YES,否则输出NO。
这道题一个星期前看到的,当时觉得好难,想了好几个方法都觉得是自己在乱搞,没有什么完整性。
于是上网看了题解后自己实现。
题解参考资料:
http://www.cnblogs.com/q-c-y/p/5660107.html
http://www.voidcn.com/blog/David_Jett/article/p-6089310.html
——————
方法1:
初始化一个数组用来存放每个数和起点的差值,
然后枚举0 - 9 每个数按差值走是否合法,如果有多个合法则为NO,否则为YES。
代码如下:
#include<cstdio> #include<iostream> #include<cstring> using namespace std ; struct node { int x,y; }; node a[] = {3,1,0,0,0,1,0,2,1,0,1,1,1,2,2,0,2,1,2,2}; // 以键盘1为坐标(0,0) 建立坐标系,每个数字坐标 int main() { string s ; int n ; cin >> n >> s ; node b[10] ; // 用来存储每个数字与起点直接的差值 node origin ; // 起点 int cnt = 0 ; // 可行数; int vis[4][3] ; memset( vis , -1 , sizeof(vis) ) ; vis[3][0] = 0 ; vis[3][2] = 0 ; origin.x = a[ s[0] - '0' ] .x ; origin.y = a[ s[0] - '0' ] .y ; for( int i = 0 ; i < n ; i++ ) { b[i].x = a[ s[i] - '0' ].x - origin.x ; b[i].y = a[ s[i] - '0' ].y - origin.y ; } //px , py 为枚举时当前坐标位置 int px , py ; for( int i = 0 ; i <= 9 ; i++ ) { int flag = 1 ; for( int j = 0 ; j< n ; j++ ) { px = a[i].x + b[j].x ; py = a[i].y + b[j].y ; if( px >= 0 && px <= 3 && py >=0 && py <= 2 && vis[px][py] ) continue ; else { flag = 0 ; cout << px << ' ' << py << endl ; break; } } if( flag == 1) cnt++; } if( cnt == 1) cout << "YES" << endl; else cout << "NO" << endl ; return 0 ; }
(1)
学到了通过memset( vis , -1 , sizeof( vis) ) 的方法,以前的我可能会用两个循环赋1,学到了-1一样可以这样的效果(memset只能初始化数组为-1 或者0 )
学到了sizeof(vis) 的表示方法,如果是我以前可能会用sizeof( int ) * 3 * 4
(2)
对于布尔代数一直小瞧了,一开始写过一个版本的:
if( px >= 0 && px <= 3 && py >=0 && py <= 2
&& ( px != 3 && py != 0 ) && ( px != 3 && py != 2 )
结果样例都过不了,后来改成:
if( px >= 0 && px <= 3 && py >=0 && py <= 2
&& ( px != 3 && (py != 0 || py != 2 ) )
WA在test10
数据:
Input
2 10
Output
NO
Answer
YES
看起来是0有关的问题。
明明读起来自己很顺口的 , “px不等于3并且py不等于2” 这样的。还是有点小瞧逻辑学了,以后注意这方面。
方法2:
如果有多解,那么一定可以通过对其中一个解进行上下左右平移等到其他解,所以本题思路是对边界判定,如果数列中出现了边界数字,则显然不能向某个方向移动。
代码如下:
#include<iostream> #include<cstring> using namespace std ; int main() { int n ; string s ; cin >> n >> s ; int L=1,R=1,U=1,D=1; for( int i = 0 ; i < n ; i++ ) { if( s[i] - '0' == 1 || s[i] - '0' == 2 || s[i] - '0' == 3 ) U = 0 ; if(s[i] - '0' == 1 || s[i] - '0' == 4 || s[i] - '0' == 7 ) L = 0 ; if(s[i] - '0' == 3 || s[i] - '0' == 6 || s[i] - '0' == 9 ) R = 0; if(s[i] - '0' == 0) L=0,R=0,D=0; if(s[i] - '0' == 7 || s[i] - '0' == 9 ) D = 0 ; } if( U == 0 && L == 0 && R == 0 && D == 0 ) cout <<"YES"<< endl ; else cout << "NO" << endl ; }
最后: