国境线，C++ Why WA?

Question

【题目描述】
Anaik大陆上一共有k个国家，为了争夺国土，各国之间常年战争不断。身为大陆的守护女神，Kiana决定重新为各个国家划分领土以终结战事。

具体来说，Anaik大陆可以看作是一个n行m列的网格，其中某些格子并不宜居，所以这些格子不被分给任何一个国家。每个国家都有一个首都，其中第i个国家的首都位于网格的第x行第y列，Kiana认为如果一个宜居的格子到第i个国家的首都的最短距离严格小于到其它国家首都的最短距离，则这个格子应被划分为第i个国家的国土。在计算距离时，每个格子被视为和它上下左右四个格子连通且距离为1，不宜居的格子不和任何格子连通。

Kiana发现按照上述方式，可能存在一些宜居的格子不能被分给任何一个国家作为国土，这种格子就称为国境线。现在Kiana想知道，大陆上总共有多少个格子属于国境线。由于她不会算，所以希望由你来告诉她。

特别的，如果某个格子不和任何一个国家的首都连通，那么Kiana认为它既不是任何一个国家的国土也不属于国境线。

【输入格式】
第一行包含三个正整数n、m和k，分别表示大陆上网格的行数、列数和国家数。

接下来k行，第i行包含两个正整数x和y，表示第i个国家首都位于第x行第y列。

接下来一行包含一个非负整数q，表示大陆上有q个格子不宜居。

接下来q行，每行包含两个正整数x和y，表示第x行第y列是一个不宜居的格子。

数据保证所有国家的首都互不相同，所有输入的不宜居格子互不相同，且没有一个国家的首都所在格子是不宜居的。

【输出格式】
输出一行一个正整数，表示总共有多少个格子属于国境线。

【样例输入 #1】
3 3 2
1 1
3 3
2
1 2
3 1
【样例输出 #1】
1

---

我的代码：

# include <bits/stdc++.h>

# define I return

# define AK 0

# define IOI ;

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

struct node {

    int x, y, dis;

} ;

const int inf = 1e9, dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};

int n, m, k, x, y, dis[3005][3005], sum;

queue <node> q;

int main () {

    ios::sync_with_stdio (0);

    cin.tie (0);

    cout.tie (0);

    memset (dis, -1, sizeof dis);

    cin >> n >> m >> k;

    while (k --)
        cin >> x >> y, q.push ({x, y, dis[x][y] = 0});

    cin >> k;

    while (k --)
        cin >> x >> y, dis[x][y] = inf;

    while (! q.empty ()) {

        const node t = q.front ();

        q.pop ();

        for (int i = 0; i < 4; ++ i) {

            x = t.x + dx[i], y = t.y + dy[i];

            if (x && y && x <= n && y <= m && dis[x][y] < inf)
                if (~dis[x][y]) {

                    if (dis[x][y] <= t.dis)
                        continue ;

                    if (dis[x][y] <= t.dis + 1)
                        ++ sum;
//                    cerr << t.x << ',' << t.y << "->" << x << ',' << y << ':' << t.dis << "->" << dis[x][y] << '\n';
                    dis[x][y] = inf;

                } else
                    q.push ({x, y, dis[x][y] = t.dis + 1});

        }

    }

    cout << sum;

    I AK IOI

}

Why WA?

Answer 1

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

struct Position {
    int x, y;
};

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    
    vector<Position> capitals(k);
    for (int i = 0; i < k; ++i) {
        cin >> capitals[i].x >> capitals[i].y;
        --capitals[i].x; // Convert to 0-based index
        --capitals[i].y;
    }
    
    int q;
    cin >> q;
    vector<vector<bool>> uninhabitable(n, vector<bool>(m, false));
    for (int i = 0; i < q; ++i) {
        int x, y;
        cin >> x >> y;
        uninhabitable[x-1][y-1] = true; // Convert to 0-based index
    }
    
    vector<vector<vector<int>>> distance(k, vector<vector<int>>(n, vector<int>(m, INT_MAX)));
    vector<vector<int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    // BFS for each capital
    for (int idx = 0; idx < k; ++idx) {
        queue<Position> q;
        auto& dist = distance[idx];
        const auto& capital = capitals[idx];
        q.push(capital);
        dist[capital.x][capital.y] = 0;
        
        while (!q.empty()) {
            Position pos = q.front();
            q.pop();
            
            int x = pos.x;
            int y = pos.y;
            
            for (auto& dir : directions) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                
                if (nx >= 0 && ny >= 0 && nx < n && ny < m && !uninhabitable[nx][ny] && dist[nx][ny] == INT_MAX) {
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }
    
    int borderCount = 0;
    
    // Determine borderlines
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (uninhabitable[i][j]) continue;
            
            int minDist = INT_MAX;
            int minCount = 0;
            
            for (int idx = 0; idx < k; ++idx) {
                if (distance[idx][i][j] < minDist) {
                    minDist = distance[idx][i][j];
                    minCount = 1;
                } else if (distance[idx][i][j] == minDist) {
                    minCount++;
                }
            }
            
            if (minCount > 1) {
                borderCount++;
            }
        }
    }
    
    cout << borderCount << endl;
    
    return 0;
}