P2895 [USACO08FEB] Meteor Shower S

语言问题引发的惨案

题目本身不难，简单的BFS，但是写出来明明思路感觉没有问题，却不是答案错就是爆队列。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

struct Node {
	int x, y;
};

const int N = 305;
int map[N][N];
int ans[N][N];
queue<Node> q;
int m, xi, yi, ti;
int ANS = 0x7fffffff;

int walk[5][2] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}, {0, 0}};

bool is_dir(int x, int y) {
	return x >= 0 && x <= N && y >= 0 && y <= N;
}

void BFS() {
	q.push({0, 0});
	ans[0][0] = 0;
	while (!q.empty()) {
		Node temp = q.front();
		q.pop();
		int x = temp.x, y = temp.y;
		if (map[x][y] == 0x7f)
		{
			ANS = ans[x][y];
			return;
		}
		for (int i = 0; i < 4; i++) {
			int dx = x + walk[i][0], dy = y + walk[i][1];
			if (is_dir(dx, dy) && ans[dx][dy] == -1 && map[dx][dy] > ans[x][y] + 1) {
				ans[dx][dy] = ans[x][y] + 1;
				q.push({dx, dy});
			}
		}
	}
}

int main() {
	memset(map, 0x7f, sizeof(map));
	memset(ans, -1, sizeof(ans));
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> xi >> yi >> ti;
		for (int i = 0; i < 5; i++) {
			int dx = xi + walk[i][0], dy = yi + walk[i][1];
			if (is_dir(dx, dy)) {
				map[dx][dy] = min(map[dx][dy], ti);
			}
		}
	}
	BFS();
	if (ANS == 0x7fffffff) {
		printf("-1");
	} else {
		printf("%d", ANS);
	}
	return 0;
}

无所谓，时间会给出答案，三天之后终于突发奇想，开始调memset，先是输出了

cout << (map[0][0] == 0x7f)

然后惊奇的发现，byd这个表达式为假。

这才记起来memset这玩意，赋值并不是直接赋值，而是 按字节赋值。

所以memset(map, 0x7f, sizeof(map));之后，是按照一个字节\(7f\)来赋值，赋值满int的四个字节。

$7f = 0111 1111$0

\(map_ (i,j) = 0111 1111 0111 1111 0111 1111 0111 = 2139062143\)

所以赋值出来是\(2139062143\)！而我BFS的终止条件判断却仍在用\(0x7f\)，导致了爆队列。

语言不扎实，什么都白搭！

AC code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

struct Node {
	int x, y;
};

const int N = 305;
int map[N][N];
int ans[N][N];
queue<Node> q;
int m, xi, yi, ti;
int ANS = 0x7fffffff;

int walk[5][2] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}, {0, 0}};

bool is_dir(int x, int y) {
	return x >= 0 && x <= N && y >= 0 && y <= N;
}

void BFS() {
	q.push({0, 0});
	ans[0][0] = 0;
	while (!q.empty()) {
		Node temp = q.front();
		q.pop();
		int x = temp.x, y = temp.y;
		if (map[x][y] >= 10000)
		{
			ANS = ans[x][y];
			return;
		}
		for (int i = 0; i < 4; i++) {
			int dx = x + walk[i][0], dy = y + walk[i][1];
			if (is_dir(dx, dy) && ans[dx][dy] == -1 && map[dx][dy] > ans[x][y] + 1) {
				ans[dx][dy] = ans[x][y] + 1;
				q.push({dx, dy});
			}
		}
	}
}

int main() {
	memset(map, 0x7f, sizeof(map));
	memset(ans, -1, sizeof(ans));
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> xi >> yi >> ti;
		for (int i = 0; i < 5; i++) {
			int dx = xi + walk[i][0], dy = yi + walk[i][1];
			if (is_dir(dx, dy)) {
				map[dx][dy] = min(map[dx][dy], ti);
			}
		}
	}
	BFS();
	if (ANS == 0x7fffffff) {
		printf("-1");
	} else {
		printf("%d", ANS);
	}
	return 0;
}