poj1475 Pushing Boxes（BFS）

题目链接

题意

推箱子游戏。输入迷宫、箱子的位置、人的位置、目标位置，求人是否能把箱子推到目标位置，若能则输出推的最少的路径，如果有多条步数相同的推的最少的路径，则输出总步数（人走的步数+推箱子的步数）最少的那条路径；若不能把箱子推到目标位置，则输出Impossible.

思路

先求出箱子到目标位置的最短路径（bfs_box），在bfs1推箱子的过程中，根据推的方向和箱子的位置得到人的位置，再求得人到达这个位置的最短路（bfs_person）即可。

代码

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <string>

 #include <queue>

 using namespace std;

 struct Node

 {

     int br, bc;        //box_row,box_col

     int pr, pc;        //person_row,person_col

     string ans;

     Node() {}

     Node(int br, int bc, int pr, int pc, string ans) :br(br), bc(bc), pr(pr), pc(pc), ans(ans) {}

 };

 const int N = ;

 int m, n;

 char maze[N][N];

 int dir[][] = { {-, }, {, }, {, -}, {, } };

 char push[] = { 'N', 'S', 'W', 'E' };

 char walk[] = { 'n', 's', 'w', 'e' };

 int br, bc;

 int pr, pc;

 int tr, tc;

 bool ok(int r, int c)

 {

     if (r >=  && r < m && c >=  && c < n && maze[r][c] != '#')

         return true;

     return false;

 }

 string tmp;

 bool bfs_person(int sr, int sc, int er, int ec, Node node)

 {

     tmp = "";

     int visit[N][N];

     memset(visit, , sizeof(visit));

     queue<Node> q;

     q.push(Node(-, -, sr, sc, ""));

     visit[sr][sc] = ;

     visit[node.br][node.bc] = ;    //注意

     while (!q.empty())

     {

         Node cur = q.front();

         q.pop();

         if (cur.pr == er && cur.pc == ec)

         {

             tmp = cur.ans;

             return true;

         }

         for (int i = ; i < ; i++)

         {

             int nr = cur.pr + dir[i][];

             int nc = cur.pc + dir[i][];

             if (ok(nr, nc) && !visit[nr][nc])

             {

                 visit[nr][nc] = ;

                 string ans = cur.ans + walk[i];

                 q.push(Node(-, -, nr, nc, ans));

             }

         }

     }

     return false;

 }

 string bfs_box()

 {

     int visit[N][N];

     memset(visit, , sizeof(visit));

     queue<Node> q;

     q.push(Node(br, bc, pr, pc, ""));

     visit[br][bc] = ;

     while (!q.empty())

     {

         Node cur = q.front();

         q.pop();

         if (cur.br == tr && cur.bc == tc)

             return cur.ans;

         for (int i = ; i < ; i++)

         {

             int nr = cur.br + dir[i][];

             int nc = cur.bc + dir[i][];

             int pre_r = cur.br - dir[i][];

             int pre_c = cur.bc - dir[i][];

             if (ok(nr, nc) && ok(pre_r, pre_c) && !visit[nr][nc])

             {

                 if (bfs_person(cur.pr, cur.pc, pre_r, pre_c, cur))

                 {

                     visit[nr][nc] = ;

                     Node next;

                     next.br = nr;

                     next.bc = nc;

                     next.pr = cur.br;

                     next.pc = cur.bc;

                     next.ans = cur.ans + tmp + push[i];

                     q.push(next);

                 }

             }

         }

     }

     return "Impossible.";

 }

 int main()

 {

     //freopen("poj1475.txt", "r", stdin);

     int cnt = ;

     while (cin >> m >> n && m)

     {

         for (int i = ; i < m; i++)

         {

             for (int j = ; j < n; j++)

             {

                 cin >> maze[i][j];

                 if (maze[i][j] == 'S')

                 {

                     pr = i;

                     pc = j;

                 }

                 else if (maze[i][j] == 'B')

                 {

                     br = i;

                     bc = j;

                 }

                 else if (maze[i][j] == 'T')

                 {

                     tr = i;

                     tc = j;

                 }

             }

         }

         printf("Maze #%d\n", ++cnt);

         cout << bfs_box() << endl << endl;

     }

     return ;

 }