- #include#include#include#define MAX_N 100#define MAX_M 100 using namespace std;
- const int INF = 100000000;
- typedef pair < int,
- int > P;
- char maze[MAX_N][MAX_M + 1];
- int N,
- M;
- int sx,
- sy;
- int gx,
- gy;
- int d[MAX_N][MAX_M];
- int dx[4] = {
- 1,
- 0,
- -1,
- 0
- },
- dy[4] = {
- 0,
- 1,
- 0,
- -1
- };
- void bfs();
- int main() {
- scanf("%d%d", &N, &M);
- for (int i = 0; i) {
- scanf("%s", maze[i]);
- }
- for (int i = 0; i) {
- for (int j = 0; j) {
- if (maze[i][j] == 'S') {
- sx = i;
- sy = j;
- }
- if (maze[i][j] == 'G') {
- gx = i;
- gy = j;
- }
- }
- }
- bfs();
- printf("%d", d[gx][gy]);
- return 0;
- }
- void bfs() {
- queue que;
- for (int i; i) {
- for (int j = 0; j) {
- d[i][j] = INF;
- }
- }
- que.push(P(sx, sy));
- d[sx][sy] = 0;
- while (que.size()) {
- //从队列的最前端取出元素
- P p = que.front();
- que.pop();
- if (p.first == gx && p.second == gy) break;
- for (int i = 0; i < 4; i++) {
- int nx = p.first + dx[i],
- ny = p.second + dy[i];
- if (maze[nx][ny] != '#' && nx >= 0 && nx = 0 && nyINF) {
- que.push(P(nx, ny));
- d[nx][ny] = d[p.first][p.second] + 1;
- }
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2093264.html