学步园

从大一暑假开始就想A的题，虽然很水的吧...

#include <stdio.h><br /> #include <queue><br /> using namespace std;<br /> struct Node<br /> {<br /> int key;<br /> int sx, sy, bx, by;<br /> bool operator < (const Node &oth) const<br /> {<br /> return key > oth.key;<br /> }<br /> };<br /> const int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // E W S N<br /> const char word[4] = {'e', 'w', 's', 'n'};<br /> const char Word[4] = {'E', 'W', 'S', 'N'};<br /> int n, m, _sx, _sy, _bx, _by, _tx, _ty;<br /> char mp[21][21];<br /> bool flag[20][20][20][20];<br /> char way[20][20][20][20];<br /> priority_queue<Node> Q;<br /> bool bound(int x, int y)<br /> {<br /> return x >= 0 && x < n && y >= 0 && y < m;<br /> }<br /> bool BFS()<br /> {<br /> Node now, nxt;<br /> while (!Q.empty()) Q.pop();<br /> memset(flag, 0, sizeof(flag));<br /> now.bx = _bx; now.by = _by;<br /> now.sx = _sx; now.sy = _sy;<br /> now.key = 0;<br /> flag[now.bx][now.by][now.sx][now.sy] = 1;<br /> way[now.bx][now.by][now.sx][now.sy] = 'X';<br /> Q.push(now);<br /> while (!Q.empty())<br /> {<br /> now = Q.top();<br /> Q.pop();<br /> if (now.bx == _tx && now.by == _ty)<br /> {<br /> _bx = now.bx; _by = now.by;<br /> _sx = now.sx; _sy = now.sy;<br /> return true;<br /> }<br /> for (int i = 0; i < 4; i++)<br /> {<br /> nxt.sx = now.sx + dir[i][0];<br /> nxt.sy = now.sy + dir[i][1];<br /> if (!bound(nxt.sx, nxt.sy) || mp[nxt.sx][nxt.sy] == '#')<br /> continue;<br /> if (nxt.sx == now.bx && nxt.sy == now.by)<br /> {<br /> nxt.bx = now.bx + dir[i][0];<br /> nxt.by = now.by + dir[i][1];<br /> nxt.key = 160000;<br /> if (!bound(nxt.bx, nxt.by) || mp[nxt.bx][nxt.by] == '#')<br /> continue;<br /> }<br /> else<br /> {<br /> nxt.bx = now.bx;<br /> nxt.by = now.by;<br /> nxt.key = 1;<br /> }<br /> if (flag[nxt.bx][nxt.by][nxt.sx][nxt.sy])<br /> continue;<br /> nxt.key += now.key;<br /> flag[nxt.bx][nxt.by][nxt.sx][nxt.sy] = 1;<br /> way[nxt.bx][nxt.by][nxt.sx][nxt.sy] = (now.bx == nxt.bx && now.by == nxt.by) ? word[i] : Word[i];<br /> Q.push(nxt);<br /> }<br /> }<br /> return false;<br /> }<br /> void FindPath(int bx, int by, int sx, int sy)<br /> {<br /> char c = way[bx][by][sx][sy];<br /> switch (way[bx][by][sx][sy])<br /> {<br /> case 'e': FindPath(bx, by, sx - dir[0][0], sy - dir[0][1]); break;<br /> case 'w': FindPath(bx, by, sx - dir[1][0], sy - dir[1][1]); break;<br /> case 's': FindPath(bx, by, sx - dir[2][0], sy - dir[2][1]); break;<br /> case 'n': FindPath(bx, by, sx - dir[3][0], sy - dir[3][1]); break;<br /> case 'E': FindPath(bx - dir[0][0], by - dir[0][1], sx - dir[0][0], sy - dir[0][1]); break;<br /> case 'W': FindPath(bx - dir[1][0], by - dir[1][1], sx - dir[1][0], sy - dir[1][1]); break;<br /> case 'S': FindPath(bx - dir[2][0], by - dir[2][1], sx - dir[2][0], sy - dir[2][1]); break;<br /> case 'N': FindPath(bx - dir[3][0], by - dir[3][1], sx - dir[3][0], sy - dir[3][1]); break;<br /> case 'X': return;<br /> }<br /> printf("%c", way[bx][by][sx][sy]);<br /> }<br /> int main()<br /> {<br /> int cas = 1;<br /> while (scanf("%d %d", &n, &m), n || m)<br /> {<br /> getchar();<br /> for (int i = 0; i < n; i++)<br /> {<br /> gets(mp[i]);<br /> }<br /> for (int i = 0; i < n; i++)<br /> {<br /> for (int j = 0; j < m; j++)<br /> {<br /> if (mp[i][j] == 'S') _sx = i, _sy = j;<br /> else if (mp[i][j] == 'B') _bx = i, _by = j;<br /> else if (mp[i][j] == 'T') _tx = i, _ty = j;<br /> }<br /> }<br /> printf("Maze #%d/n", cas++);<br /> if (BFS()) FindPath(_bx, _by, _sx, _sy);<br /> else printf("Impossible.");<br /> printf("/n/n");<br /> }<br /> return 0;<br /> }