dfs 剪枝40分 求助
查看原帖
dfs 剪枝40分 求助
702161
abcaawtq楼主2023/9/24 08:49
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int p[N][N];
int n,m,t;
int a,b,c,d,cnt;
int dx[4] = {1,-1,0,0},dy[4] = {0,0,1,-1};
void dfs(int x,int y,int tt){
	if(x == c && y == d && tt == 0){
		cnt ++;
		return;
	}
	if(tt == 0 || (abs(x - c) + abs(y - d) > tt))return ;
	for(int i = 0; i < 3; i ++){
		int xx = dx[i] + x;
		int yy = dy[i] + y;
		if(xx <= n && yy <= m && xx > 0 && yy > 0  && p[xx][yy]){
			dfs(xx,yy,tt - 1);
		}
	}
}
int main(){
	cin >> n >> m >> t ;
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			char c;
			cin >> c;
			if(c == '.') p[i][j] = 1;
		}
	}
	cin >> a >> b >> c >> d ;
	dfs(a,b,t);
	cout << cnt ;
	return 0;
}
2023/9/24 08:49
加载中...