题解 | 走迷宫

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

int n, m;
int s1, s2, e1, e2;
char str[1010][1010];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int head = 1;
int tail = 1;
int arr[1000100][4];

int main()
{
    cin >> n >> m;
    cin >> s1 >> s2 >> e1 >> e2;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> str[i][j];
        }
    }
    arr[1][1] = s1;
    arr[1][2] = s2;
    arr[1][3] = 0;
    if (str[e1][e2] == '*')
    {
        cout << "-1";
        return 0;
    }
    while (head <= tail)
    {
        for (int i = 0; i < 4; i++)
        {
            int tx = dx[i] + arr[head][1];
            int ty = dy[i] + arr[head][2];
            if (str[tx][ty] == '.' && tx <= n && ty <= m && tx >= 1 && ty >= 1)
            {
                tail++;
                str[tx][ty] = '*';
                arr[tail][1] = tx;
                arr[tail][2] = ty;
                arr[tail][3] = arr[head][3] + 1;
            }
            if (tx == e1 && ty == e2)
            {
                cout << arr[tail][3];
                exit(0);
            }
        }
        head++;
    }
    cout << "-1";
    return 0;
}