第2题

给定 $n\times n$ 个方格构成的矩阵，刷满了红色和蓝色。现在要矩阵的一些格子刷上紫色，使得矩阵同时满足以下两个条件：从 $(1,1)$ 走到 $(n,n)$，保证存在一条路径使其只经过红色和紫色；从 $(1,n)$ 走到 $(n,1)$，保证存在一条路径使其只经过蓝色和紫色。注意，行动时只可以往任何一个方向前进，至少要将多少格子刷成紫色才能使以上两个条件成立呢？

#include<iostream>
#include<deque>
int n;
const int maxn = 500;
char c[maxn][maxn];
int dist[maxn][maxn];
int solve(int sx, int sy, int tx, int ty, char color) {
    bool visited[maxn][maxn] = {false};
    std::deque<std::pair<int, int>> q;
    q.push_back({sx, sy});
    visited[sx][sy] = true;
    ____(1)____ ;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop_front();
        const int dx[4] = {1, -1, 0, 0};
        const int dy[4] = {0, 0, -1, 1};
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (0 <= nx and nx < n and 0 <= ny and ny < n) {
                if (not visited[nx][ny]) {
                    visited[nx][ny] = true;
                    if ( ____(2)____ ) {
                        dist[nx][ny] = dist[x][y];
                        q.push_front({nx, ny});
                    }
                    else {
                        dist[nx][ny] = ____(3)____ ;
                        q.push_back({nx, ny});
                    }
                }
            }
        }
    }
    return ____(4)____ ;
}

int main()
{
    std::cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cin >> c[i][j];
        }
    }
    std::cout << ____(5)____ + ____(6)____ << "\n";
}

(2) 处应填（ ）。

{{ select(1) }}

• dist[nx][ny] == 0
• dist[nx][ny] == 1
• c[nx][ny] == color
• c[nx][ny] == c[x][y]