/*這道題我原本是將斜線迷宮擴大為原來的兩倍，但是在這種情況下對于在斜的方向上的搜索會變的較容易出錯，所以參考了別人的思路后將迷宮擴展為原來的3倍，這樣就變成一般的迷宮問題了*/

1 #include"iostream" 2 #include"stdio.h" 3 #include"algorithm" 4 #include"cmath" 5 #include"string.h" 6 #include"ctype.h" 7 #include"queue" 8 #include"map" 9 #define mx 300 10 using namespace std; 11 int w,h; 12 int maze[mx][mx]; 13 char m; 14 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; 15 int visited[mx][mx]; 16 int cnt;//記錄圈的個數 17 int mxlen;//記錄最長圈的長度 18 int len;//記錄當前圈的長度 19 int flag;//標記是否構成圈 20 bool judge(int x,int y) 21 { 22 if(x>=0&&x<3*h&&y>=0&&y<3*w) return true;//判斷點是否出界 23 else return false; 24 } 25 void dfs(int x,int y) 26 { 27 int k,dx,dy; 28 for(k=0;k<4;k++) 29 { 30 dx=x+dir[k][0]; 31 dy=y+dir[k][1]; 32 if(judge(dx,dy)) 33 { 34 if(!visited[dx][dy]&&!maze[dx][dy]) 35 { 36 visited[dx][dy]=1; 37 len++; 38 dfs(dx,dy); 39 } 40 } 41 else //邊界上的點肯定不構成圈。。。 42 {flag=0;} 43 // cout<<len<<endl; 44 } 45 } 46 int main() 47 { 48 int i,j,k; 49 int count1=0; 50 while(cin>>w>>h,w||h) 51 { 52 count1++; 53 memset(maze,0,sizeof(maze)); 54 for(i=0;i<h;i++) 55 { 56 getchar(); 57 for(j=0;j<w;j++) 58 { 59 scanf("%c",&m); 60 if(m=='/') 61 { 62 maze[3*i+2][3*j]=1;maze[3*i+1][3*j+1]=1;maze[3*i][3*j+2]=1; 63 } 64 else 65 { 66 maze[3*i][3*j]=1;maze[3*i+1][3*j+1]=1;maze[3*i+2][3*j+2]=1; 67 } 68 } 69 } 70 for(i=0;i<3*h;i++) 71 for(j=0;j<3*w;j++) 72 {visited[i][j]=maze[i][j];} 73 mxlen=0; 74 cnt=0; 75 for(i=0;i<3*h;i++) 76 { 77 for(j=0;j<3*w;j++) 78 { 79 if(maze[i][j]==0&&!visited[i][j]) 80 { 81 len=1; 82 flag=1; 83 visited[i][j]=1; 84 dfs(i,j); 85 if(flag) 86 { 87 cnt++; 88 if(len>mxlen) mxlen=len; 89 } 90 } 91 } 92 } 93 cout<<"Maze #"<<count1<<":"<<endl; 94 if(cnt==0) cout<<"There are no cycles."<<endl<<endl; 95 else 96 cout<<cnt<<" Cycles; "<<"the longest has length "<<mxlen/3<<'.'<<endl<<endl; 97 } 98 return 0; 99 } View Code

?

轉載于:https://www.cnblogs.com/acm-jing/p/4245504.html

總結

以上是生活随笔為你收集整理的uva705--slash maze的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。