sos,修改了好久也不知道为什么错了的代码

Question

#include<bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
char chess[1005][1005], mark[1005][1005];
int n, m, x, y, ans=1, sum, re[1005][1005],u;
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
typedef pair<int, int> pll;
queue<pll> q;
int check(int a, int b) {
    return mark[a][b];
}
int bfs(int x, int y)
{
    u = ans;
    q.push({ x, y });
    while (q.size()) {
        auto t = q.front();
        //if (re[x][y] != -1)return re[x][y];
        mark[x][y] = chess[x][y];
        q.pop();
        for (int i = 0; i < 4; i++) {
            int a = t.first + dx[i], b = t.second + dy[i];
            if (a <= n && b <= n && a > 0 && b > 0) {
                
                if (chess[a][b] != chess[t.first][t.second]) {
                    if (check(a, b) == -1) {
                        mark[a][b] = chess[a][b];
                        ans++;
                        //re[a][b] = ans;
                        q.push({ a,b });
                        chess[x][y] = chess[a][b];

                    }

                }
            }

        }
    }
    if (u == ans) {
        return u;
    }
    else return ans-u+1;

}

int main()
{
    memset(mark, -1, sizeof mark);
    //memset(re, -1, sizeof(re));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> chess[i][j];
        }
    }
    for (int i = 1; i <= m; i++)
    {
        

        cin >> x >> y;
        cout << bfs(x,y);
    
        if (i != m) {
            cout << endl;
        }
    }

}

https://www.luogu.com.cn/problem/P1141

只有样例过了。但是不知道为什么错了改了好久了

Answer 1

Au_ust 晚上好🌙🌙🌙
本答案参考通义千问

你的代码在处理bfs函数时，re数组可能并不是用来存储路径长度的，而是可能用于记录某个格子已经被访问过的次数。因此，re[a][b] = ans;这行代码应该是错误的，因为ans记录的是到达新格子的次数，而不是路径长度。

另外，check函数可能需要检查mark数组来判断当前位置是否已经访问过，但这里并未使用它。我猜测check函数可能应该用来检查当前位置是否为1，因为题目描述中提到从0移动到1，反之亦然。

修复后的代码：

#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
char chess[1005][1005], mark[1005][1005];
int n, m, x, y, ans = 1, sum, re[1005][1005], u;
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, 1, 0, -1 };
typedef pair<int, int> pll;
queue<pll> q;

// 更新check函数，用于检查当前位置是否为1
int check(int a, int b) {
    return chess[a][b] == '1';
}

// bfs 函数中移除对re数组的更新，并将ans作为路径长度返回
int bfs(int x, int y) {
    u = ans;
    q.push({ x, y });
    while (!q.empty()) {
        auto t = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int a = t.first + dx[i], b = t.second + dy[i];
            if (a <= n && b <= n && a > 0 && b > 0) {
                if (chess[a][b] != chess[t.first][t.second]) {
                    if (!check(a, b)) {
                        ans++;
                        q.push({ a, b });
                        chess[x][y] = chess[a][b]; // 更新起点格子的状态
                    }
                }
            }
        }
    }
    return ans;
}

int main() {
    memset(mark, -1, sizeof mark);
    // 不再使用re数组
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> chess[i][j];
        }
    }
    for (int i = 1; i <= m; i++) {
        cin >> x >> y;
        cout << bfs(x, y) << endl; // 将输出结果改为ans，而不是re
    }
}

解决方案：

1. 修复check函数：
   • 将mark[a][b] = chess[a][b];替换为chess[a][b] == '1' ? true : false;。
2. 修改bfs函数：
   • 删除re[a][b] = ans;，并将ans作为返回值，表示路径长度。
3. 移除re数组的使用，因为似乎并不需要这个数组。