• + 0 comments

    simply O(n^3) algo

    void update(int I, int J, int i, int j, vector<vector<bool>>& visited, vector<vector<int>>& minPath, queue<pair<int, int>>& Q) {
        if (visited[i][j]) return;
        visited[i][j] = true;
        minPath[i][j] = minPath[I][J] + 1;
        Q.push(make_pair(i, j));
        return;
    }
    
    int minimumMoves(int n, vector<vector<char>> grid, int startX, int startY, int goalX, int goalY) {
        vector<vector<bool>> visited(n + 2, vector<bool>(n + 2));
        vector<vector<int>> minPath(n + 2, vector<int>(n + 2, -1));
        queue<pair<int, int>> Q;
        Q.push(make_pair(startX, startY));
        visited[startX][startY] = true;
        minPath[startX][startY] = 0;
        while (!Q.empty()) {
            int I = Q.front().first, J = Q.front().second;
            for (int i=1; I - i > 0; i++) {
                if (grid[I-i][J] == 'X') break;
                update(I, J, I-i, J, visited, minPath, Q);
            }
            for (int i=1; I + i < n+1; i++) {
                if (grid[I+i][J] == 'X') break;
                update(I, J, I+i, J, visited, minPath, Q);
            }
            for (int j=1; J - j > 0; j++) {
                if (grid[I][J-j] == 'X') break;
                update(I, J, I, J-j, visited, minPath, Q);
            }
            for (int j=1; J + j < n+1; j++) {
                if (grid[I][J+j] == 'X') break;
                update(I, J, I, J+j, visited, minPath, Q);
            }
            Q.pop();
        }
        return minPath[goalX][goalY];
    }
    
    int main()
    {
        int n, startX, startY, goalX, goalY;
        string s;
        cin >> n;
        vector<vector<char>> grid(n + 2, vector<char>(n + 2));
        for (int i = 1; i <= n; i++) {
            cin >> s;
            for (int j = 1; j <= n; j++) grid[i][j] = s[j - 1];
        }
        cin >> startX >> startY >> goalX >> goalY;
        cout << minimumMoves(n, grid, startX + 1, startY + 1, goalX + 1, goalY + 1);
    }