第四个点RE(虽然开大数组过了但是还是很好奇为什么会RE)
查看原帖
第四个点RE(虽然开大数组过了但是还是很好奇为什么会RE)
590283
lunatics楼主2022/7/26 00:36

AC代码如下,问题发生在队列的定义,最开始我使用的是int queue[900][2],然后代码除了第四个点RE其余全AC。后来把数组长度开到100000,就过了。

目前随便测了几次,队列开到70000也是RE。但是理论上最多只有900个点,并且一定达不到900,队列开900就够了,为什么会出现RE的情况?求大佬赐教。

#include<stdio.h>

int queue[100000][2], matrix[40][40];
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,-1,0,1 };

void BFS(int x, int y) {
	int head = 0, tail = 1;
	queue[head][0] = x; queue[head][1] = y;
	while (head != tail) {
		for (int i = 0; i < 4; i++) {
			if (matrix[queue[head][0] + dx[i]][queue[head][1] + dy[i]] == 0) {
				queue[tail][0] = queue[head][0] + dx[i];
				queue[tail][1] = queue[head][1] + dy[i];
				tail++;
			}
		}
		matrix[queue[head][0]][queue[head][1]] = 100;
		head++;
	}
}

int main(void) {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &matrix[i][j]);
		}
	}
	for (int i = 0; i <= n + 1; i++) {
		matrix[i][0] = 100;
		matrix[i][n + 1] = 100;
		matrix[0][i] = 100;
		matrix[n + 1][i] = 100;
	}
	for (int i = 1; i <= n; i++) {
		if (matrix[i][1] == 0) {
			BFS(i, 1);
		}
		if (matrix[i][n] == 0) {
			BFS(i, n);
		}
		if (matrix[1][i] == 0) {
			BFS(1, i);
		}
		if (matrix[n][i] == 0) {
			BFS(n, i);
		}
	}
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			if (matrix[i][j] == 0)
				matrix[i][j] = 2;
			if (matrix[i][j] == 100)
				matrix[i][j] = 0;
		}
	}
	for (int i = 1; i < n; i++) {
		for (int j = 1; j <= n; j++) {
			printf("%d ", matrix[i][j]);
		}
		printf("\n");
	}
	for (int j = 1; j < n; j++) {
		printf("%d ", matrix[n][j]);
	}
	printf("%d", matrix[n][n]);
}
2022/7/26 00:36
加载中...