133NSON edited 2 年,8 月前

#include <iostream>
#include <vector>
// #include <queue>

using namespace std;

struct point1
{
    int x;
    int y;
    int n;
    bool b;
};

struct myQue
{
    point1 ap[500000] = {0};
    int fir;
    int back;
    point1 front()
    {
        return ap[fir];
    }
    void push(int x, int y, int n, bool b)
    {
        point1 tmp{x, y, n, b};
        ap[back++] = tmp;
        if (back == 500000) {
            back = 0;
        }
    }
    bool empty()
    {
        return back == fir;
    }
    void pop()
    {
        fir++;
        if (fir == 500000) {
            fir = 0;
        }
    }
};


int bfs(vector<vector<char>>, int, int);

int main()
{
    int n, m, sx, sy;

    while (cin >> n >> m)
    {
        vector<vector<char>> a;
        a.resize(n);
        for (int i{}; i < n; i++) {
            for (int j{}; j < m; j++) {
                char tmp;
                cin >> tmp;
                a[i].push_back(tmp);
                if (tmp == 'S') {
                    sx = i;
                    sy = j;
                }
            }
        }
        int can = bfs(a, sx, sy);
        if (can) {
            cout << can;
        } else {
            cout << "impossible";
        }
        cout << endl;
    }

    return 0;
}

// int bfs(vector<vector<char>> a, int x, int y)
// {
//     queue<point1> q;
//     q.push({x, y, 0, 0});
//     for ( ; !(q.empty()); a[q.front().x][q.front().y] = '#', q.pop()) {
//         if (q.front().b) {
//             q.push({q.front().x, q.front().y, q.front().n, false});
//             continue;
//         }
//         if ((q.front().x + 1) < a.size() && a[q.front().x + 1][q.front().y] == '.') {
//             q.push({q.front().x + 1, q.front().y, q.front().n + 1, false});
//         } else if ((q.front().x + 1) < a.size() && a[q.front().x + 1][q.front().y] == 'X') {
//             q.push({q.front().x + 1, q.front().y, q.front().n + 2, true});
//         } else if ((q.front().x + 1) < a.size() && a[q.front().x + 1][q.front().y] == 'T') {
//             return q.front().n + 1;
//         }
//         if ((q.front().x - 1) >= 0 && a[q.front().x - 1][q.front().y] == '.') {
//             q.push({q.front().x - 1, q.front().y, q.front().n + 1, false});
//         } else if ((q.front().x - 1) >= 0 && a[q.front().x - 1][q.front().y] == 'X') {
//             q.push({q.front().x - 1, q.front().y, q.front().n + 2, true});
//         } else if ((q.front().x - 1) >= 0 && a[q.front().x - 1][q.front().y] == 'T') {
//             return q.front().n + 1;
//         }
//         if ((q.front().y + 1) < a[0].size() && a[q.front().x][q.front().y + 1] == '.') {
//             q.push({q.front().x, q.front().y + 1, q.front().n + 1, false});
//         } else if ((q.front().y + 1) < a[0].size() && a[q.front().x][q.front().y + 1] == 'X') {
//             q.push({q.front().x, q.front().y + 1, q.front().n + 2, true});
//         } else if ((q.front().y + 1) < a[0].size() && a[q.front().x][q.front().y + 1] == 'T') {
//             return q.front().n + 1;
//         }
//         if ((q.front().y - 1) >= 0 && a[q.front().x][q.front().y - 1] == '.') {
//             q.push({q.front().x, q.front().y - 1, q.front().n + 1, false});
//         } else if ((q.front().y - 1) >= 0 && a[q.front().x][q.front().y - 1] == 'X') {
//             q.push({q.front().x, q.front().y - 1, q.front().n + 2, true});
//         } else if ((q.front().y - 1) >= 0 && a[q.front().x][q.front().y - 1] == 'T') {
//             return q.front().n + 1;
//         }
//     }
//     return 0;
// }

int bfs(vector<vector<char>> a, int x, int y)
{
    myQue q;
    q.fir = 0;
    q.back = 0;
    q.push(x, y, 0, 0);
    for ( ; !(q.empty()); a[q.front().x][q.front().y] = '#', q.pop()) {
        if (q.front().b) {
            q.push(q.front().x, q.front().y, q.front().n, false);
            continue;
        }
        if ((q.front().x + 1) < a.size() && a[q.front().x + 1][q.front().y] == '.') {
            q.push(q.front().x + 1, q.front().y, q.front().n + 1, false);
        } else if ((q.front().x + 1) < a.size() && a[q.front().x + 1][q.front().y] == 'X') {
            q.push(q.front().x + 1, q.front().y, q.front().n + 2, true);
        } else if ((q.front().x + 1) < a.size() && a[q.front().x + 1][q.front().y] == 'T') {
            return q.front().n + 1;
        }
        if ((q.front().x - 1) >= 0 && a[q.front().x - 1][q.front().y] == '.') {
            q.push(q.front().x - 1, q.front().y, q.front().n + 1, false);
        } else if ((q.front().x - 1) >= 0 && a[q.front().x - 1][q.front().y] == 'X') {
            q.push(q.front().x - 1, q.front().y, q.front().n + 2, true);
        } else if ((q.front().x - 1) >= 0 && a[q.front().x - 1][q.front().y] == 'T') {
            return q.front().n + 1;
        }
        if ((q.front().y + 1) < a[0].size() && a[q.front().x][q.front().y + 1] == '.') {
            q.push(q.front().x, q.front().y + 1, q.front().n + 1, false);
        } else if ((q.front().y + 1) < a[0].size() && a[q.front().x][q.front().y + 1] == 'X') {
            q.push(q.front().x, q.front().y + 1, q.front().n + 2, true);
        } else if ((q.front().y + 1) < a[0].size() && a[q.front().x][q.front().y + 1] == 'T') {
            return q.front().n + 1;
        }
        if ((q.front().y - 1) >= 0 && a[q.front().x][q.front().y - 1] == '.') {
            q.push(q.front().x, q.front().y - 1, q.front().n + 1, false);
        } else if ((q.front().y - 1) >= 0 && a[q.front().x][q.front().y - 1] == 'X') {
            q.push(q.front().x, q.front().y - 1, q.front().n + 2, true);
        } else if ((q.front().y - 1) >= 0 && a[q.front().x][q.front().y - 1] == 'T') {
            return q.front().n + 1;
        }
    }
    return 0;
}

Comments