穿越雷区 BFS解法

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;

const int N = 101;
bool vis[N][N] = {false};
char a[N][N];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

struct Node {
    int x, y;
    int step;
    Node(int a, int b, int s) {
        x = a;
        y = b;
        step = s;
    }
};

int main()
{
    int n;
	queue<Node> s;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
            if (a[i][j] == 'A') {
                s.push(Node(i, j, 0));
            }
        }
    }

    while (s.size() > 0) {
        Node front = s.front();
        s.pop();
        if (a[front.x][front.y] == 'B') {
            cout << front.step << endl;
            break;
        }
       
        for (int i = 0; i < 4; i++) {
            int tx = front.x + dx[i];
            int ty = front.y + dy[i];
            if (tx < 0 || tx >= n || ty < 0 || ty >= n || vis[tx][ty]
                || (a[front.x][front.y] == a[tx][ty])) {
                continue;
            }
            vis[tx][ty] = true;
            s.push(Node(tx, ty, front.step + 1));
        }
    }
    
    return 0;
}