各位大佬，这道题为什么80分，求救一下

问题讨论区 基础段
1

题目描述 有一个仅由数字 0 与 1 组成的 NN 格迷宫。 若你位于一格 0 上，那么你可以移动到相邻 4 格中的某一格 1 上； 同样若你位于一格 1 上，那么你可以移动到相邻 4 格中的某一格 0 上。 你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。 输入格式 第1行为两个正整数 N,M。（N\le1000;M\le100000） 下面 N 行，每行 N 个字符，字符只可能是 0 或者 1，字符之间没有空格。 接下来 M 行，每行 2 个用空格分隔的正整数 i,j，对应了迷宫中第 i 行第 j 列的一个格子，询问从这一格开始能移动到多少格。 输出格式 M 行，对于每个询问输出相应答案。 样例 Input 1 2 2 01 10 1 1 2 2 Output 1 4 4题目描述 有一个仅由数字 0 与 1 组成的 NN 格迷宫。 若你位于一格 0 上，那么你可以移动到相邻 4 格中的某一格 1 上； 同样若你位于一格 1 上，那么你可以移动到相邻 4 格中的某一格 0 上。 你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。 输入格式 第1行为两个正整数 N,M。（N\le1000;M\le100000） 下面 N 行，每行 N 个字符，字符只可能是 0 或者 1，字符之间没有空格。 接下来 M 行，每行 2 个用空格分隔的正整数 i,j，对应了迷宫中第 i 行第 j 列的一个格子，询问从这一格开始能移动到多少格。 输出格式 M 行，对于每个询问输出相应答案。 样例 Input 1 2 2 01 10 1 1 2 2 Output 1 4 4
#include<bits/stdc++.h>
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
char a[1005][1005];
int vis[1005][1005];
int ans[5005];
int n, m, sum;
void dfs(int x, int y, int id) {
vis[y] = id;
ans[id]++;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 1 || ny < 1 || nx > n || ny > n) {
continue;
}
if (a[y] == a[nx][ny]) {
continue;
}
if (vis[nx][ny] != 0) {
continue;
}
dfs(nx, ny, id);
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
while (m–) {
int x, y;
cin >> x >> y;
if (vis[y] == 0) {
sum++;
dfs(x, y, sum);
}
cout << ans[vis[y]] << endl;
}
return 0;
} 错哪了

1 个赞
2

可以格式化一下吗，就是重新编辑一下，放代码的时候点一下 </>

1 个赞
3 
#include<bits/stdc++.h>
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
char a[1005][1005];
int vis[1005][1005];
int ans[5005];
int n, m, sum;
void dfs(int x, int y, int id) {
    vis[x][y] = id; 
    ans[id]++; 
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 1 || ny < 1 || nx > n || ny > n) {
		   continue;
	    }
        if (a[x][y] == a[nx][ny]) {
		   continue; 
	    }
        if (vis[nx][ny] != 0) {
		   continue; 
	    }
        dfs(nx, ny, id);
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    while (m--) {
        int x, y;
        cin >> x >> y;
        if (vis[x][y] == 0) {
            sum++;
            dfs(x, y, sum);
        }
        cout << ans[vis[x][y]] << endl;
    }
    return 0;
}
4

题目编号

5

01迷宫

6

加个标记数组vis试试，我记得01迷宫可以回走的

7

不行

8 
 vis[nx][ny] == id || a[x][y] == a[nx][ny]

加上这个试试？

9

dfs 里的 if 都写在一起，

void dfs (int x, int y, int id) {
	// 联通块问题考虑递归结束；
		// 无路可走的时候 
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		
		if (nx < 1 || ny < 1 || nx > n || ny > n || vis[nx][y] == t || a[x][y] == a[nx][ny]) {
			continue;
		}
		
		ans[t]++;
		vis[nx][ny] = t;
		
		dfs(nx, ny, id);
	}
}

dfs 先这样写写看，主函数里不会再问吧，我也只会个 dfs 了

10

谢谢