HDU1010(DFS+奇偶剪枝)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,t,a,b,c,d;
char map[10][10];
bool vis[10][10];
int dir[10][10] = {{0,1},{0,-1},{-1,0},{1,0}};
bool flag;

void dfs(int x,int y,int time){
	if(flag) return;
	if(map[x][y] == 'D' && time == t){
		flag = true;
		return;
	}
	if((abs(x-c)+abs(y-d)) % 2 != (t-time)%2) return; 
	//奇偶剪枝  某一可达路线 = 当前坐标到终点的最短路径(可以用曼哈顿定理通过坐标求出) + 偏移量(偏移量一定为偶数)
	// 又因为 偶数+偶数=偶数  奇数+偶数等于奇数
	//所以 某一可达路线的奇偶性和当前坐标到终点的最短路径奇偶性一致
	//所以可以通过当前坐标到终点的最短路径的奇偶性与剩下的时间的奇偶性比较,如果不一致,直接剪枝
	 
	if(t-time < abs(x-c)+abs(y-d)) return; // 可达性剪枝  如果剩下的时间比最短路径还小,就return 
	
	
	for(int i = 0;i<4;i++){
		int xx = x + dir[i][0];
		int yy = y + dir[i][1];
		
		if(xx > 0 && xx <= n && yy > 0 && yy <=m && !vis[xx][yy] && map[xx][yy] !='X'){
			vis[xx][yy] = 1;
			dfs(xx,yy,time+1);
			vis[xx][yy] = 0;
		}
	}
	return;
}

int main(){
	while(1){
			cin  >> n >> m >> t;
			if(n == 0 || m ==  0 || t == 0) return 0;
	memset(map,'0',sizeof(map)); 
	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=m;j++){
			cin >> map[i][j];
			if(map[i][j] == 'S') {
				a = i;
				b = j;
			}		
			if(map[i][j] == 'D'){
				c = i;
				d = j;
			}
		}
	}
	memset(vis,0,sizeof(vis));
	int minn = abs(a-c)+abs(b-d);
	if(t < minn || (t-minn)%2 == 1){ //如果给的时间比最短路径少 或者  偏差量为奇数 可以直接排除 
		cout << "NO" << endl;
		continue; 
	}
	
	flag = false;
	vis[a][b] = 1;
	dfs(a,b,0);
	
	if(flag) cout <<"YES" << endl;
	else cout << "NO" << endl; 
}
	
	
	return 0;
}

上一篇:Math02Practise


下一篇:python基础语法和函数学习