求助一下,感觉好像没有什么问题,直接暴力就过,但是记忆化搜索好像错了一部分
  • 板块P1605 迷宫
  • 楼主ahardstone
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/10/18 15:57
  • 上次更新2023/10/27 07:01:15
查看原帖
求助一下,感觉好像没有什么问题,直接暴力就过,但是记忆化搜索好像错了一部分
819995
ahardstone楼主2022/10/18 15:57
#include <bits/stdc++.h>
using namespace std;
int n, m, t, sx, sy, fx, fy, step = 0;
int dp[10][10] = {0};
int moves[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int book[10][10] = {0};
int dfs(int x, int y) {
	if (dp[x][y]) {
		return dp[x][y];
	}
	for (int i = 0; i < 4; i++) {
		int nx = x + moves[i][0];
		int ny = y + moves[i][1];
		if (nx < 1 || ny < 1 || nx > n || ny > m || book[nx][ny]) {
			continue;
		}
		book[nx][ny] = 1;
		dp[x][y] += dfs(nx, ny);
		book[nx][ny] = 0;
	}
	return dp[x][y];
}
int main() {
	cin >> n >> m >> t >> sx >> sy >> fx >> fy;
	while (t--) {
		int p, r;
		cin >> p >> r;
		book[p][r] = 1;
	}
	book[sx][sy] = 1;
	dp[fx][fy] = 1;
	cout << dfs(sx, sy) << '\n';
	return 0;
}
2022/10/18 15:57
加载中...