篝火问题求助

学生 · 2025 年9 月 6 日 12:00

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node {
	int x, y;
} f[1000005];
map<int, int> mp;
signed main() {
	int n, r, c;
	cin >> n >> r >> c;
	for (int i = 1; i <= n; i++) {
		char c;
		cin >> c;
		int dx = 0, dy = 0;
		if (c == 'N') {
			dx = -1;
		} else if (c == 'S') {
			dx = 1;
		} else if (c == 'W') {
			dy = -1;
		} else {
			dy = 1;
		}
		f[i].x = f[i - 1].x + dx;
		f[i].y = f[i - 1].y + dy;
		int k = f[i].x * 1000000007ll + f[i].y;
		if (i > 0 && (f[i].x != 0 || f[i].y != 0)) {
			if (!mp.count(k)) {
				mp[k] = i;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		int x = f[i].x - r;
		int y = f[i].y - c;
		int k = x * 1000000007ll + y;
		if (mp[k] == 0 || mp.count(k) || (f[k].x != 0 || f[k].y != 0)) {
			cout << 1;
		} else {
			cout << 0;
		}
	}
}

样例全部输出1，求助。

CZF2919 · 2025 年9 月 6 日 12:10

会不会是c变量重名了？

学生 · 2025 年9 月 6 日 12:12

这个我试过，如果是暴力的话没问题

CZF2919 · 2025 年9 月 6 日 12:13

懂了，你输出那个循环不能mp全部ok了之后查，不然肯定都是1的。你要在输入的同时输出

学生 · 2025 年9 月 6 日 12:14

kasaoluo:

int x = f[i].x - r;
		int y = f[i].y - c;
		int k = x * 1000000007ll + y;
		if (mp[k] == 0 || mp.count(k) || (f[k].x != 0 || f[k].y != 0)) {
			cout << 1;
		} else {
			cout << 0;
		}

就是把上面这一段移到

if (i > 0 && (f[i].x != 0 || f[i].y != 0)) {
			if (!mp.count(k)) {
				mp[k] = i;
			}
		}

下面吗？

CZF2919 · 2025 年9 月 6 日 12:14

应该是的

CZF2919 · 2025 年9 月 6 日 12:15

还有你的(f[k].x != 0 || f[k].y != 0)明显不对啊，k怎么回事这个数组的下标呢？

学生 · 2025 年9 月 6 日 12:15

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node {
	int x, y;
} f[1000005];
map<int, int> mp;
signed main() {
	int n, r, c;
	cin >> n >> r >> c;
	for (int i = 1; i <= n; i++) {
		char c;
		cin >> c;
		int dx = 0, dy = 0;
		if (c == 'N') {
			dx = -1;
		} else if (c == 'S') {
			dx = 1;
		} else if (c == 'W') {
			dy = -1;
		} else {
			dy = 1;
		}
		f[i].x = f[i - 1].x + dx;
		f[i].y = f[i - 1].y + dy;
		int k = f[i].x * 1000000007ll + f[i].y;
		if (i > 0 && (f[i].x != 0 || f[i].y != 0)) {
			if (!mp.count(k)) {
				mp[k] = i;
			}
		}
		int x = f[i].x - r;
		int y = f[i].y - c;
		k = x * 1000000007ll + y;
		if (mp[k] == 0 || mp.count(k) || (f[k].x != 0 || f[k].y != 0)) {
			cout << 1;
		} else {
			cout << 0;
		}
	}
}

输出一样

学生 · 2025 年9 月 6 日 12:16

我后面有点写不下去了，直接乱搞了

CZF2919 · 2025 年9 月 6 日 12:16

f[i].x = f[i - 1].x + dx;
		f[i].y = f[i - 1].y + dy;
		int k = f[i].x * 1000000007ll + f[i].y;
				mp[k] = i;
      int x = f[i].x - r;
		int y = f[i].y - c;
		k = x * 1000000007ll + y;
		if (mp.count(k)) {
			cout << 1;
		} else {
			cout << 0;
		}

CZF2919 · 2025 年9 月 6 日 12:17

你的if语句有点乱，改成上面的代码应该没问题了

学生 · 2025 年9 月 6 日 12:21

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node {
	int x, y;
} f[1000005];
map<int, int> mp;
signed main() {
	int n, r, c;
	cin >> n >> r >> c;
	for (int i = 1; i <= n; i++) {
		char c;
		cin >> c;
		int dx = 0, dy = 0;
		if (c == 'N') {
			dx = -1;
		} else if (c == 'S') {
			dx = 1;
		} else if (c == 'W') {
			dy = -1;
		} else {
			dy = 1;
		}
		f[i].x = f[i - 1].x + dx;
		f[i].y = f[i - 1].y + dy;
		int k = f[i].x * 1000000007ll + f[i].y;
		if (i > 0 && (f[i].x != 0 || f[i].y != 0)) {
			if (!mp.count(k)) {
				mp[k] = i;
			}
		}
		int x = f[i].x - r;
		int y = f[i].y - c;
		k = x * 1000000007ll + y;
		if (mp.count(k)) {
			cout << 1;
		} else {
			cout << 0;
		}
	}
}

是这样吗？全输出0了

@CZF2919

CZF2919 · 2025 年9 月 6 日 12:22

这里不需要判断

学生 · 2025 年9 月 6 日 12:23

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node {
	int x, y;
} f[1000005];
map<int, int> mp;
signed main() {
	int n, r, c;
	cin >> n >> r >> c;
	for (int i = 1; i <= n; i++) {
		char c;
		cin >> c;
		int dx = 0, dy = 0;
		if (c == 'N') {
			dx = -1;
		} else if (c == 'S') {
			dx = 1;
		} else if (c == 'W') {
			dy = -1;
		} else {
			dy = 1;
		}
		f[i].x = f[i - 1].x + dx;
		f[i].y = f[i - 1].y + dy;
		int k = f[i].x * 1000000007ll + f[i].y;
		int x = f[i].x - r;
		int y = f[i].y - c;
		k = x * 1000000007ll + y;
		if (mp.count(k)) {
			cout << 1;
		} else {
			cout << 0;
		}
	}
}

也是0啊

CZF2919 · 2025 年9 月 6 日 12:23

因为你就算移动回(0,0)去了也没关系

CZF2919 · 2025 年9 月 6 日 12:23

不需要判断不是不需要mp

学生 · 2025 年9 月 6 日 12:24

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node {
	int x, y;
} f[1000005];
map<int, int> mp;
signed main() {
	int n, r, c;
	cin >> n >> r >> c;
	for (int i = 1; i <= n; i++) {
		char c;
		cin >> c;
		int dx = 0, dy = 0;
		if (c == 'N') {
			dx = -1;
		} else if (c == 'S') {
			dx = 1;
		} else if (c == 'W') {
			dy = -1;
		} else {
			dy = 1;
		}
		f[i].x = f[i - 1].x + dx;
		f[i].y = f[i - 1].y + dy;
		int k = f[i].x * 1000000007ll + f[i].y;
		mp[k] = i;
		int x = f[i].x - r;
		int y = f[i].y - c;
		k = x * 1000000007ll + y;
		if (mp.count(k)) {
			cout << 1;
		} else {
			cout << 0;
		}
	}
}

还全是0

CZF2919 · 2025 年9 月 6 日 12:28

c重名了

CZF2919 · 2025 年9 月 6 日 12:28

int和char

学生 · 2025 年9 月 6 日 12:29

哦我知道了因为换到一个循环里了所以重名就有问题了