广州怎么建设一个网站,京津冀协同发展的首要任务有,互动营销的概念,辽宁工业大学教务管理系统第六题#xff1a;T6位置互换
标签#xff1a;广度优先搜索题意#xff1a;给定一个矩形地图#xff0c;地图中 . . .代表可以走的空地#xff1b; # \# #代表不可以走的墙壁#xff1b; 1 1 1表示小爱初始的位置#xff1b; 2 2 2表示小艾初始的位置。小爱和小艾可以上…第六题T6位置互换
标签广度优先搜索题意给定一个矩形地图地图中 . . .代表可以走的空地 # \# #代表不可以走的墙壁 1 1 1表示小爱初始的位置 2 2 2表示小艾初始的位置。小爱和小艾可以上下左右走或原地不动不可以移动到对方当前的位置求经过多少轮之后小爱和小艾可以实现互换位置。题解把小爱和小艾的整体移动跑 b f s bfs bfs开个四维 v i s vis vis数组标记一下各自走同步的情况进行位移的过程中需要把各自 4 4 4个方向即 4 4 4x 4 4 4种情况都跑一下。跑 b f s bfs bfs的过程中需要注意几个细节
如果小爱或者小艾某个人已经跑到对应互换的终点了就原地保持不动。如果发生了当前跑到的两个位置互换的情况要跳过。比如小爱在 ( 2 , 2 ) (2,2) (2,2)位置要往右走到 ( 2 , 3 ) (2,3) (2,3)小艾在 ( 2 , 3 ) (2,3) (2,3)位置要往左走到 ( 2 , 3 ) (2,3) (2,3)。移动到同一个格子的时候需要让其中一个人原地不动另一个人走到这个各自上。
整道题细节比较多和需要考虑的点比较多同学们在写的过程中要注意细节的处理。代码
#include bits/stdc.h
using namespace std;struct node {// 当前小爱坐标(x1,y1) 小艾坐标(x2,y2) 步数int x1, y1, x2, y2, step;
}st;
int n, m;
int dx[4] {0, 0, -1, 1};
int dy[4] {-1, 1, 0, 0};
char a[50][50];
bool vis[50][50][50][50];bool check(int x, int y) {return x 1 x n y 1 y m a[x][y] ! #;
}void bfs() {queuenode q;q.push(st);vis[st.x1][st.y1][st.x2][st.y2] 1;while (!q.empty()) {node p q.front();q.pop();if (p.x1 st.x2 p.y1 st.y2 p.x2 st.x1 p.y2 st.y1) {cout p.step;return ;}// 枚举小爱和小艾的所有方向组合for (int i 0; i 4; i)for (int j 0; j 4; j) {int nx1 p.x1 dx[i], ny1 p.y1 dy[i];int nx2 p.x2 dx[j], ny2 p.y2 dy[j];if (nx1 p.x2 ny1 p.y2 nx2 p.x1 ny2 p.y1) continue;// 如果已经到终点, 原地保持不动if (p.x1 st.x2 p.y1 st.y2) nx1 p.x1, ny1 p.y1;if (p.x2 st.x1 p.y2 st.y1) nx2 p.x2, ny2 p.y2;if (check(nx1, ny1) check(nx2, ny2)) {if (nx1 nx2 ny1 ny2) { // 移动到同一个格子的情况if (!vis[nx1][ny1][p.x2][p.y2]) {vis[nx1][ny1][p.x2][p.y2] 1;q.push({nx1, ny1, p.x2, p.y2, p.step 1});}if (!vis[p.x1][p.y1][nx2][ny2]) {vis[p.x1][p.y1][nx2][ny2] 1;q.push({p.x1, p.y1, nx2, ny2, p.step 1});}} else { // 不是移动到同一个格子的情况if (!vis[nx1][ny1][nx2][ny2]) {vis[nx1][ny1][nx2][ny2] 1;q.push({nx1, ny1, nx2, ny2, p.step 1});}}}}}cout No Solution;
}int 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] 1) st.x1 i, st.y1 j;if (a[i][j] 2) st.x2 i, st.y2 j;}bfs();return 0;
}
