1215：迷宫
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。
【输入】
第1行是测试数据的组数k，后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 ≤ n ≤ 100)，表示迷宫的规模是n * n的。接下来是一个n * n的矩阵，矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。
【输出】
k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。
【输入样例】
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0
【输出样例】
YES
NO
【来源】
No
1. //深搜 2. #include<iostream> 3. #include<cstdio> 4. using namespace std; 5. int dx[4]={0,1,0,-1}; 6. int dy[4]={-1,0,1,0}; 7. int k,n,ya,xa,yb,xb; 8. char str; 9. bool s[101][101],tem; 10. int nx,ny; 11. int dfs(int y,int x) 12. { 13. for(int i=0;i<4;i++){ 14. nx=x+dx[i]; 15. ny=y+dy[i]; 16. if(nx>=0&&nx<n&&ny>=0&&ny<n&&(!s[ny][nx])){ 17. s[ny][nx]=true; 18. if(nx==xb&&ny==yb){ 19. cout<<"YES"<<endl; 20. tem=true; 21. break; 22. } 23. else dfs(ny,nx); 24. } 25. } 26. } 27. int main() 28. { 29. cin>>k; 30. for(int t=1;t<=k;t++){ 31. cin>>n; 32. tem=false; 33. for(int i=0;i<n;i++) 34. for(int j=0;j<n;j++){ 35. cin>>str; 36. if(str=='.') s[i][j]=false; 37. else s[i][j]=true; 38. } 39. cin>>ya>>xa>>yb>>xb; 40. if(s[ya][xa]||s[yb][xb]){ 41. cout<<"NO"<<endl; 42. continue; 43. } 44. else dfs(ya,xa); 45. if(!tem) cout<<"NO"<<endl; 46. } 47. return 0; 48. }
1. //广搜 2. #include<iostream> 3. #include<cstdio> 4. #include<cstring> 5. using namespace std; 6. int dx[4]={0,1,0,-1}; 7. int dy[4]={-1,0,1,0}; 8. bool a[101][101]; 9. char c[101][101]={0}; 10. int dl[10005][4]; 11. int main() 12. { 13. int k,n,x,y,xl,yl,xx,yy,t,w,f,s; 14. cin>>k; 15. for(int s=1;s<=k;s++){ 16. memset(a,0,sizeof(a)); 17. memset(dl,0,sizeof(dl)); 18. t=1,w=2,f=0; 19. cin>>n; 20. for(int i=0;i<n;i++) 21. for(int j=0;j<n;j++) cin>>c[i][j]; 22. cin>>x>>y>>xl>>yl; 23. if(c[x][y]=='#'||c[xl][yl]=='#') cout<<"NO"<<endl; 24. else { 25. a[x][y]=true; 26. dl[1][1]=x; 27. dl[1][2]=y; 28. while(t<w){ 29. for(int i=0;i<4;i++){ 30. xx=dl[t][1]+dx[i]; 31. yy=dl[t][2]+dy[i]; 32. if(xx<0||xx>n-1||yy<0||yy>n-1) continue; 33. if(c[xx][yy]!='#'&&!a[xx][yy]){ 34. a[xx][yy]=true; 35. dl[w][1]=xx; 36. dl[w][2]=yy; 37. w++; 38. } 39. if(xx==xl&&yy==yl){ 40. cout<<"YES"<<endl; 41. f=1; 42. break; 43. } 44. } 45. if(f==1) break; 46. t++; 47. } 48. if(f==0) cout<<"NO"<<endl; 49. } 50. } 51. return 0; 52. }
