题意：推箱子的题目，求最短的路径，如果推的最短一样的话，就算上走的最短
【POJ - 1475 Pushing Boxes】思路：首先我们记录状态：箱子的位置和人的位置，我们先BFS箱子的最短，然后我们可以通过推的方向得到人的位置，然后再BFS人是否能到这里的最短路
#include
#include
#include
#include
#include
using namespace std;
const int MAXN = 50;
struct status{
int person_x,person_y;
int box_x,box_y;
string ans;
}p,q;
struct node{
int x,y;
string ans;
}P,Q;
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};
char Pm[]={'s', 'n', 'e', 'w'};
char Pb[]={'S', 'N', 'E', 'W'};
int visP[MAXN][MAXN],visB[MAXN][MAXN];
char G[MAXN][MAXN];
int sx,sy,ex,ey,bx,by;
int r,c;
int check(int x, int y){
if (x >= 0 && x< r && y >= 0 && y < c)
return true;
return false;
}int bfs2(int start_x, int start_y, int end_x, int end_y){
memset(visP, 0, sizeof(visP));
P.x = start_x;
P.y = start_y;
P.ans = "";
visP[P.x][P.y] = 1;
visP[p.box_x][p.box_y] = 1;
queue qq;
qq.push(P);
while (!qq.empty()){
P = qq.front();
qq.pop();
if (P.x == end_x && P.y == end_y)
return true;
for (int i = 0;
i < 4;
i++){
int nx = P.x + dx[i];
int ny = P.y + dy[i];
if (check(nx, ny) && G[nx][ny] != '#' && !visP[nx][ny]){
visP[nx][ny] = 1;
Q.ans = P.ans + Pm[i];
Q.x = nx;
Q.y = ny;
qq.push(Q);
}
}
}
return false;
}int bfs(){
memset(visB, 0, sizeof(visB));
p.person_x = sx;
p.person_y = sy;
p.box_x = bx;
p.box_y = by;
p.ans = "";
visB[bx][by] = 1;
queue st;
st.push(p);
while (!st.empty()){
p = st.front();
st.pop();
for (int i = 0;
i < 4;
i++){
int nx = p.box_x + dx[i];
int ny = p.box_y + dy[i];
int tx = p.box_x - dx[i];
int ty = p.box_y - dy[i];
if (check(tx, ty) && G[tx][ty] != '#' && check(nx, ny) &&
G[nx][ny] != '#' && !visB[nx][ny]){
if (bfs2(p.person_x, p.person_y, tx, ty)){
visB[nx][ny] = 1;
q.person_x = p.box_x;
q.person_y = p.box_y;
q.box_x = nx;
q.box_y = ny;
q.ans = p.ans+P.ans+Pb[i];
if (nx == ex && ny == ey)
return true;
st.push(q);
}
}
}
}
return false;
}int main(){
int cas = 1;
while (scanf("%d%d", &r, &c) != EOF && r+c){
for (int i = 0;
i < r;
i++){
scanf("%s", G[i]);
for (int j = 0;
j < c;
j++){
if (G[i][j] == 'S'){
sx = i;
sy = j;
}
if (G[i][j] == 'T'){
ex = i;
ey = j;
}
if (G[i][j] == 'B'){
bx = i;
by = j;
}
}
}
printf("Maze #%d\n", cas++);
if (bfs())
printf("%s\n", q.ans.c_str());
else printf("Impossible.\n");
printf("\n");
}
return 0;
} 推荐阅读
- 题解|【HNOI2017】大佬-dalao
- #|蓝桥杯 - [2013年第四届真题]危险系数(割点)
- 搜索|Wannafly模拟赛3-B 贝伦卡斯泰露（DFS）
- 思维题|Maze（CodeForces - 377A ）（思维，广搜）
- 搜索|[CF235E]Number Challenge
- online|Codeforces #245 (Div. 2)C. Xor-tree（DFS&&贪心
- 算法|《自制搜索引擎》笔记
- 搜索|业务同学入门搜索，推荐的一些套路方案
- ACM|Pushing Boxes （poj 1475 嵌套bfs）
- POJ 1475 Pushing Boxes