走迷宫让我想起数据结构的课设,不过是反过来找到出口的最短路径,方法差不多,用的bfs,想法是从bfs找到每个点的最短路径,其中最长的就是最难到出口的.
不过这图确实让我比较蛋疼,开始以为一个符号算一格,定义的迷宫长宽为2h+1,2w+1...后来一跑发现是17,和例子的9差这么多...仔细一看原来迷宫还是h*w大小的...
后来来想着怎么改进存储,想了好一会发现改起来还真麻烦,后来脑子一转,我无非多走了1倍,于是把结果(tmax+1)/2竟然过了...
有点要注意,bfs时遇到第一次访问的点时,存进去当前已走步数,如果再次访问到,若发现第二次步数小于已存的,则替换为更小的,同时入队列.反之不入列。对了 我是从出口开始往里走，这个要注意下
1 /* 2 3 ID: hubiao cave 4 5 PROG: maze1 6 7 LANG: C++ 8 9 */ 10 11 12 13 14 #include<iostream> 15 16 #include<fstream> 17 18 #include<string> 19 #include<utility> 20 21 #include<deque> 22 using namespace std; 23 24 25 char maze[202][80]; 26 int rec[202][80]; 27 int W,H; 28 pair<int,int> exit1,exit2; 29 typedef pair<pair<int,int>,int> cp; 30 deque<cp> deq; 31 32 void bfs(pair<int,int> &); 33 int main() 34 35 { 36 37 38 ifstream fin("maze1.in"); 39 40 ofstream fout("maze1.out"); 41 42 fin>>W>>H; 43 int cou=0; 44 string str; 45 46 getline(fin,str); 47 for(int i=0;i<=2*H;i++) 48 { 49 getline(fin,str); 50 for(int j=0;j<=2*W;j++) 51 { 52 //fin>>maze[i][j]; 53 maze[i][j]=str[j]; 54 if(maze[i][j]=='+'||maze[i][j]=='-'||maze[i][j]=='|') 55 maze[i][j]='b'; 56 else if(maze[i][j]==' '&&(i==0||i==2*H||j==0||j==2*W)) 57 { 58 cou?(exit2.first=i,exit2.second=j):(exit1.first=i,exit1.second=j); 59 maze[i][j]='b'; 60 cou++; 61 } 62 else 63 { 64 maze[i][j]=' '; 65 } 66 67 68 } 69 } 70 bfs(exit1); 71 deq.clear(); 72 bfs(exit2); 73 74 int tmax=0; 75 for(int i=0;i<=2*H;++i) 76 for(int j=0;j<=2*W;++j) 77 { 78 if(rec[i][j]>tmax) 79 tmax=rec[i][j]; 80 } 81 fout<<(tmax+1)/2<<endl; 82 return 0; 83 84 85 } 86 void bfs(pair<int,int> &exit) 87 { 88 cp temp,t2; 89 temp.first.first=exit.first; 90 temp.first.second=exit.second; 91 temp.second=0; 92 deq.push_back(temp); 93 94 while(!deq.empty()) 95 { 96 t2=deq.front(); 97 deq.pop_front(); 98 99 //north 100 if(t2.first.first>0&&maze[t2.first.first-1][t2.first.second]!='b') 101 { 102 if(rec[t2.first.first-1][t2.first.second]==0) 103 { 104 temp.first=make_pair(t2.first.first-1,t2.first.second); 105 rec[t2.first.first-1][t2.first.second]=temp.second=t2.second+1; 106 deq.push_back(temp); 107 } 108 else 109 { 110 if(rec[t2.first.first-1][t2.first.second]>t2.second+1) 111 { 112 temp.first=make_pair(t2.first.first-1,t2.first.second); 113 rec[t2.first.first-1][t2.first.second]=temp.second=t2.second+1; 114 deq.push_back(temp); 115 } 116 } 117 } 118 119 //south 120 if(t2.first.first<2*H&&maze[t2.first.first+1][t2.first.second]!='b') 121 { 122 if(rec[t2.first.first+1][t2.first.second]==0||rec[t2.first.first+1][t2.first.second]>t2.second+1) 123 { 124 temp.first=make_pair(t2.first.first+1,t2.first.second); 125 rec[t2.first.first+1][t2.first.second]=temp.second=t2.second+1; 126 deq.push_back(temp); 127 } 128 } 129 //west 130 if(t2.first.second>0&&maze[t2.first.first][t2.first.second-1]!='b') 131 { 132 if(rec[t2.first.first][t2.first.second-1]==0||rec[t2.first.first][t2.first.second-1]>t2.second+1) 133 { 134 temp.first=make_pair(t2.first.first,t2.first.second-1); 135 rec[t2.first.first][t2.first.second-1]=temp.second=t2.second+1; 136 deq.push_back(temp); 137 } 138 } 139 //east 140 if(t2.first.second<2*W&&maze[t2.first.first][t2.first.second+1]!='b') 141 { 142 if(rec[t2.first.first][t2.first.second+1]==0||rec[t2.first.first][t2.first.second+1]>t2.second+1) 143 { 144 temp.first=make_pair(t2.first.first,t2.first.second+1); 145 rec[t2.first.first][t2.first.second+1]=temp.second=t2.second+1; 146 deq.push_back(temp); 147 } 148 } 149 } 150 }