题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

const int N = 1010;

int maze[N][N];
int n;
pair<int, int> st[N][N];


void bfs(int x, int y)
{
    memset(st, -1, sizeof st);
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

    queue<pair<int, int>> q;
    q.push({x, y});
    st[x][y] = {0, 0};

    while(q.size())
    {
        auto t = q.front();
        q.pop();
        int x = t.first, y = t.second;
        if (!x && !y) return;
        for (int i = 0; i < 4; i ++)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= n) continue;
            if (maze[a][b]) continue;
            if (st[a][b].first != -1) continue;
            st[a][b] = t;
            q.push({a, b});

        }

    }

}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            cin >> maze[i][j];

    bfs(n - 1, n - 1);

    pair<int, int> end (0, 0);

    while(true)
    {
        cout << end.first << " " << end.second << endl;
        if (end.first == n - 1 && end.second == n - 1) break;
        end = st[end.first][end.second];
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla