警钟撅烂(IF you WA on#2 #7 #8)
  • 板块P1605 迷宫
  • 楼主StevenYan
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/6 16:39
  • 上次更新2025/1/7 09:44:11
查看原帖
警钟撅烂(IF you WA on#2 #7 #8)
1260548
StevenYan楼主2025/1/6 16:39

可能是
没有把起点特判为障碍物的缘故
所以起点会被计算进次数导致答案变大
附dfs code

#include <bits/stdc++.h>
using namespace std;
int n, m, t, sx, sy, fx, fy, ans = 0;
int a[10][10];

void dfs(int x, int y) {
//	cout << x << " " << y << endl;
	if (x == fx && y == fy) {
		ans++;
//		cout << "ans:" << ans << endl;
		return;
	} else {
		if (!a[x + 1][y] && x + 1 <= n) {
			a[x + 1][y] = 1;
			dfs(x + 1, y);
			a[x + 1][y] = 0;
		}
		if (!a[x - 1][y] && x - 1 >= 1) {
			a[x - 1][y] = 1;
			dfs(x - 1, y);
			a[x - 1][y] = 0;
		}
		if (!a[x][y - 1] && y - 1 >= 1) {
			a[x][y - 1] = 1;
			dfs(x, y - 1);
			a[x][y - 1] = 0;
		}
		if (!a[x][y + 1] && y + 1 <= n) {
			a[x][y + 1] = 1;
			dfs(x, y + 1);
			a[x][y + 1] = 0;
		}
	}
}

int main() {
	memset(a, 0, sizeof(a));
	cin >> n >> m >> t >> sx >> sy >> fx >> fy;
	a[sx][sy] = 1;//警钟敲烂
	for (int i = 1; i <= t; i++) {
		int x, y;
		cin >> x >> y;
		a[x][y] = 1;
	}
	dfs(sx, sy);
	cout << ans;
	return 0;
}
2025/1/6 16:39
加载中...