1212:LETTERS
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
给出一个roe×col的大写字母矩阵,一开始的位置为左上角,你可以向上下左右四个方向移动,并且不能移向曾经经过的字母。问最多可以经过几个字母。
【输入】
第一行,输入字母矩阵行数R和列数S,1≤R,S≤20。接着输出R行S列字母矩阵。
【输出】
最多能走过的不同字母的个数。
【输入样例】
3 6
HFDFFB
AJHGDH
DGAGEH
【输出样例】
6
【来源】
No
1. #include<iostream> 2. #include<cstdio> 3. #include<iomanip> 4. using namespace std; 5. int r,s; 6. char a[50][50]; 7. bool b[50][50]={0}; 8. bool p[1000]; 9. int X[4]={-1,0,1,0}; 10. int Y[4]={0,1,0,-1}; 11. int sum=0; 12. int dfs(int x,int y,int t) 13. { 14. sum=max(sum,t); 15. for(int i=0;i<4;i++){ 16. int xx=x+X[i]; 17. int yy=y+Y[i]; 18. if(xx>=1&&xx<=r&&yy>=1&&yy<=s&&(!b[xx][yy])&&(!p[a[xx][yy]])){ 19. b[xx][yy]=1; 20. p[a[xx][yy]]=1; 21. dfs(xx,yy,t+1); 22. b[xx][yy]=0; 23. p[a[xx][yy]]=0; 24. } 25. } 26. } 27. int main() 28. { 29. cin>>r>>s; 30. for(int i=1;i<=r;i++) 31. for(int j=1;j<=s;j++) cin>>a[i][j]; 32. b[1][1]=1; 33. p[a[1][1]]=1; 34. dfs(1,1,1); 35. cout<<sum; 36. return 0; 37. }