信息学奥赛一本通T1256-献给阿尔吉侬的花束(BFS)

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

class Node {

public:

    int x, y, step;

    Node(int i, int j, int s) {

        x = i;

        y = j;

        step = s;

    }

};

Node start(0, 0, 0);

Node dest(0, 0, 0);

bool visit[201][201] = {false};

char a[201][201];

int dx[4] = {1, 0, -1, 0};

int dy[4] = {0, 1, 0, -1};

int main()

{

    int t, r, c;

    cin >> t;

    for (int k = 0; k < t; k++) {

        cin >> r >> c;

        for (int i = 0; i < r; i++) {

            for (int j = 0; j < c; j++) {

                cin >> a[i][j];

                if (a[i][j] == 'S') {

                    start.x = i;

                    start.y = j;

                    start.step = 0;

                }

                else if (a[i][j] == 'E') {

                    dest.x = i;

                    dest.y = j;

                    dest.step = 0;

                }

            }

        }

        queue<Node> q;

        bool found = false;

        int res = 0;

        q.push(start);

        while (!q.empty()) {

            Node front = q.front();

            q.pop();

            if (front.x == dest.x && front.y == dest.y) {

                found = true;

                res = front.step;

                break;

            }

            for (int d = 0; d < 4; d++) {

                int tx = front.x + dx[d];

                int ty = front.y + dy[d];

                if (tx >= 0 && tx < r && ty >= 0 && ty < c 

                    && !visit[tx][ty] && a[tx][ty] != '#') {

                    visit[tx][ty] = true;

                    q.push(Node(tx, ty, front.step + 1));

                }

            }

        }

        if (found) {

            cout << res << endl;

        } else {

            cout << "oop!" << endl;

        }

        memset(visit, false, sizeof(visit));

    }

    return 0;

}