1 solutions
-
2
[USACO11OPEN] Corn Maze S
唐诗
代码后加了一些小tips（在文末）
先看题面，当看到“最短时间”时就应该直接反应到这是一个要求最短路的问题，还是走迷宫系列
考虑bfs
如我在推荐里说的，这个题考细节，有坑
那么我认为最坑的地方就是
滑梯不能标记，因为他可能只是一个中转站
看这个例子：
#####=####### ####...###### #####A####### #####@####### ############# ###A######### ###.#########在这个例子里，我们需要利用两次A滑梯，但如果标记了就会无解
剩下的就没什么了
上代码
#include<iostream> #include<queue> #define int long long using namespace std; const int dx[4]={-1,1,0,0}; const int dy[4]={0,0,-1,1}; struct node{ int x,y,cnt; }; queue<node> q; struct slide{ int xs=-1,ys=-1,xd=-1,yd=-1; }s[26]; int n,m,stx,sty,dex,dey; char a[305][305]; bool vis[305][305]; void bfs(int i,int j){ q.push({i,j,0}); vis[i][j]=1; while(!q.empty()){ node t=q.front(); q.pop(); if(t.x==dex&&t.y==dey){//到终点了 cout<<t.cnt; return; } if(a[t.x][t.y]>='A'&&a[t.x][t.y]<='Z'){//滑梯 int num=a[t.x][t.y]-'A'; if(s[num].xs!=-1&&s[num].xd!=-1){ if(t.x==s[num].xs&&t.y==s[num].ys) t.x=s[num].xd,t.y=s[num].yd;//起->终 else t.x=s[num].xs,t.y=s[num].ys;//终->起 } } for(int ppp=0;ppp<4;ppp++){//搜连通块 int nx=t.x+dx[ppp]; int ny=t.y+dy[ppp]; if(nx>0&&nx<=n&&ny>0&&ny<=m&&!vis[nx][ny]){//没有超出边界且没有被访问过 q.push({nx,ny,t.cnt+1}); vis[nx][ny]=1; } } } } signed main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>a[i][j]; if(a[i][j]=='@') stx=i,sty=j;//start else if(a[i][j]=='=') dex=i,dey=j;//destination else if(a[i][j]=='#') vis[i][j]=1;//corn else if(a[i][j]>='A'&&a[i][j]<='Z'){//slide int num=a[i][j]-'A'; if(s[num].xs==-1) s[num].xs=i,s[num].ys=j; else s[num].xd=i,s[num].yd=j; } } } bfs(stx,sty); return 0; }还有，在遇到滑梯改坐标时直接用原坐标改（点名狗叶）
top.x = tpe[(int)a[top.x][top.y] ].x,top.y = tpe[(int)a[top.x][top.y] ].y;这样第二条语句会改
在新的x坐标和原来的y坐标的点的y坐标
显然不对，所以要像文中一样搞一个临时变量来储存原来的点，再进行传送操作
求个赞QAQ
-
C24kongxiangtai
@ 2025-6-12 13:29:21
@为什么我的代码没有输出求调
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 3e2 + 10, INF = 0x3f3f3f3f; struct sit { int x, y, step; }; struct tpsit { int x, y; }; int n, m, a[N][N], sx, sy, ex, ey, ans = INF; int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; char c; tpsit tps[N], tpe[N]; queue <sit> q; void bfs(int sx, int sy) { q.push( {sx, sy, 1} ); while (q.size()) { sit top = q.front(); cout << a[top.x][top.y] << endl; a[top.x][top.y] = 0; q.pop(); if (top.x == ex and top.y == ey) { cout << top.step; return ; } if (a[top.x][top.y] > 1) { if (top.x == tps[a[top.x][top.y]].x and top.y == tps[a[top.x][top.y]].y) top.x = tpe[a[top.x][top.y]].x, top.y = tpe[a[top.x][top.y]].y; else top.x = tps[a[top.x][top.y]].x, top.y = tps[a[top.x][top.y]].y; } for (int k = 0; k < 4; k++) { int xx = top.x + dx[k]; int yy = top.y + dy[k]; if (a[xx][yy] == 1) { a[xx][yy] = 0; q.push( {xx, yy, top.step + 1} ); } } } } signed main() { cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { cin >> c; if (c == '@') sx = i, sy = j, a[i][j] = 1; else if (c == '=') ex = i, ey = j, a[i][j] = 1; else if (c == '#') a[i][j] = 0; else if (c == '.') a[i][j] = 1; else { a[i][j] = (int)c; if(tps[(int)c].x and tps[(int)c].y) tpe[(int)c].x = i, tpe[(int)c].y = j; else tps[(int)c].x = i, tps[(int)c].y = j; } } bfs(sx, sy); return 0; } -
C24liukaiwen
@ 2025-6-12 13:39:07
-
C24kongxiangtai
@ 2025-6-12 13:42:06
-
C24liukaiwen
@ 2025-6-12 13:46:06
-
C24kongxiangtai
@ 2025-6-12 13:50:18
-
C24liukaiwen
@ 2025-6-13 13:18:32
@ 我分析了这两份迷宫寻路代码，发现它们有以下几个关键区别：
主要区别
数据结构设计
第一份代码使用数值矩阵a[][]表示地图，将字符转换为数值存储
第二份代码直接使用字符矩阵a[][]存储地图，更加直观
访问标记方式
第一份代码通过将可通行的1改为0来标记已访问
第二份代码使用专门的vis[][]布尔数组标记访问状态
方向数组定义
第一份代码的方向数组顺序为：下、上、右、左
第二份代码的方向数组顺序为：上、下、左、右 滑梯处理机制
第一份代码使用两个数组tps和tpe存储滑梯的起点和终点
第二份代码使用结构体数组s[26]，通过字符转换为索引直接访问
起点终点命名
第一份代码：起点sx,sy，终点ex,ey
第二份代码：起点stx,sty，终点dex,dey
步数计数
第一份代码从1开始计数
第二份代码从0开始计数
搜索逻辑
第一份代码：只搜索值为1的格子（路径）
第二份代码：搜索所有未访问且在边界内的格子
算法影响
第一份代码的标记方式可能导致原地图信息丢失，
而第二份代码保持地图完整
第一份代码的滑梯处理需要进行 ASCII 码转换，
第二份代码直接使用字符索引
第一份代码的搜索范围更受限，第二份代码更通用
第二份代码使用专门的访问标记数组，逻辑更清晰，适合处理复杂地图
这两份代码虽然实现方式不同，但核心都是使用 BFS 算法寻找最短路径，并且都考虑了滑梯这种特殊传送门的处理。第二份代码的设计更加现代和模块化，而第一份代码则更简洁直接。
-
C24liukaiwen
@ 2025-6-13 13:19:25
-
- 1
