AC代码:
方法一(结构体的运用 + 标记): #include<iostream> #include<algorithm> #include<cstring> #include<string> #include<string.h> #include<limits.h> #include<vector> #include<deque> #include<queue> #include<stack> #include<set> #include<map> using namespace std; const int maxn = 25; char str[maxn][maxn]; int vis[maxn][maxn]; struct node { // 结构体将其信息绑定到一起 int x,y,step; } dot[maxn]; int dir[][2] = {{1,0},{-1,0},{0,1},{0,-1}}; // 方向 int n,m; int ans = 0,res = 0; int main(void) { int BFS(int start_x,int start_y); scanf("%d%d",&n,&m); for(int i = 1; i <= n; i ++) { for(int j = 0; j <= m; j ++) { // 有换行字符,所以从 0 开始 scanf("%c",&str[i][j]); } } ans = 0; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) { if(str[i][j] == '#') continue; res = BFS(i,j); ans = max(ans,res); } } cout << ans << endl; return 0; } bool Check(int x,int y) { if(x < 1 || y < 1 || x > n || y > m) return false; if(vis[x][y] || str[x][y] == '#') return false; if(str[x][y] == '.') return true; } int BFS(int start_x,int start_y) { memset(vis,0,sizeof(vis)); // 复原 int count = 0; queue<node>queues; while(!queues.empty()) queues.pop(); node first,second; first.x = start_x,first.y = start_y,first.step = 0; queues.push(first); vis[start_x][start_y] = 1; while(!queues.empty()) { first = queues.front(); queues.pop(); count = max(count,first.step); // 每次进行比较得到最大的值 for(int i = 0; i < 4; i ++) { second.x = first.x + dir[i][0]; second.y = first.y + dir[i][1]; if(!Check(second.x,second.y)) continue; // 注意这里用 ! （这里卡了好久,一定要记得自己写的Check函数返回的是什么） second.step = first.step + 1; queues.push(second); vis[second.x][second.y] = 1; } } return count; } 方法二(pair的运用,参考大佬写的，感觉相对于结构体来说,更好用一点,再次特地感谢那位无名大佬): 大致思路类似: #include<iostream> #include<algorithm> #include<cstring> #include<string.h> #include<limits.h> #include<string> #include<vector> #include<deque> #include<queue> #include<stack> #include<map> #include<set> #define P pair<int,int> #define x first #define y second using namespace std; const int maxn = 25; char str[maxn][maxn]; int num[maxn][maxn]; int dir[][2] = {{1,0},{-1,0},{0,1},{0,-1}}; int n,m,ans,res; queue<P>Q; int main(void) { int BFS(int start_x,int start_y); scanf("%d%d",&n,&m); for(int i = 1; i <= n; i ++) { for(int j = 0; j <= m; j ++) { scanf("%c",&str[i][j]); } } ans = 0,res = 0; for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++ ) { if(str[i][j] == '#') continue; res = BFS(i,j); ans = max(ans,res); } } cout << ans << endl; return 0; } bool Check(int x,int y) { if(x < 1 || y < 1 || x > n || y > m) return false; if(str[x][y] == '#' || num[x][y]) return false; if(str[x][y] == '.') return true; } int BFS(int start_x,int start_y) { P a,b; int count = 0; memset(num,0,sizeof(num)); while(!Q.empty()) Q.pop(); a.x = start_x,a.y = start_y; Q.push(a); while(!Q.empty()) { a = Q.front(); Q.pop(); count = max(count,num[a.x][a.y]); int v = num[a.x][a.y]; for(int i = 0; i < 4; i ++) { b.x = a.x + dir[i][0]; b.y = a.y + dir[i][1]; if(!Check(b.x,b.y)) continue; if(b.x != start_x || b.y != start_y) { // 要保证不会回到最初的点,因为这种方法我们没有进行标记 num[b.x][b.y] = v + 1; Q.push(b); } /* 如果不加特殊判断的话就会出现错误,下面是特殊样例: 2 2 #. #. */ } } return count; } 知识总结: 1、复习了 map 容器的运用,更加熟练。 2、对迷宫问题有了更深一步的了解，同时对 BFS 也算回顾复习了一下(Check语句一定要认真,弄清楚返回的是什么) 3、pair<int,int> 的应用，相对于结构体来说,这个的应用更方便一点。 #赛后小结:# 1、认真读题，认真读题，一定要真正读题,有可能一个小小的细节就会导致大错误。 2、大胆一点,有想法就要尝试一下。 3、坚持到比赛最后一秒,不要因为时间快到了就不去想了，也不要因为别人都做出来了而不再去尝试。···
能力有限,如有写的不到位的地方，望路过的朋友留下您的建议,在下会细心改正，万分感谢。
后续更新 ing............