HDU 1010 Tempter of the Bone(dfs+剪枝)

       题意是问从S出发,终点为D,如果能刚好k步到达终点就输出YES,否则输出NO。如果直接深搜会超时,所以这里需要进行奇偶剪枝。

        奇偶剪枝就是比如说不考虑障碍物的情况下起点为S_x,S_y,终点为E_x,E_y,那么起点到终点的最短距离为dist=|S_x-E_x|+|S_y-E_y|,当dist和题目中所需要的走的步数k同奇同偶的时候是可以走到的,否则是一定走不到的。所以这道题就是判断k 和 已经走过的步数+当前点到终点的最短距离的奇偶性是否相同。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN = 105;
char MAP[MAXN][MAXN];
int vis[MAXN][MAXN];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int n,m,k,flag,S_x,S_y,E_x,E_y;

int dist(int x1,int y1,int x2,int y2){              // 计算当前点到终点的最短距离
	return (abs(x1-x2)+abs(y1-y2));
}

void dfs(int x,int y, int step){
	if(x == E_x && y == E_y && step == k){
		flag = 1;
		return ;
	}
	if(flag)return ;
	for(int i=0;i<4;i++){
		int X = x + dir[i][0];
		int Y = y + dir[i][1];
	  if(X < 0 || Y < 0 || X >= n || Y >= m || MAP[X][Y] == 'X' || vis[X][Y]) continue;
		//if((1+step+dist(X,Y,E_x,E_y) <= k) &&((dist(X,Y,E_x,E_y)+1+step) % 2 == k % 2)){
			vis[X][Y] = 1;
			dfs(X,Y,step + 1);
			// if(flag)return ;
			vis[X][Y] = 0;
		}
	//}
}

int main()
{
	while(~scanf("%d%d%d",&n,&m,&k)){
		if(n == 0 && m == 0 && k == 0) break;
		flag = 0;
		for(int i=0;i<n;i++){
			scanf("%s",MAP[i]);
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(MAP[i][j] == 'S'){
					S_x = i;
					S_y = j;
				}
				if(MAP[i][j] == 'D'){
					E_x = i;
					E_y = j;
				}
			}
		}
		if((dist(S_x,S_y,E_x,E_y) % 2 != k % 2) || dist(S_x,S_y,E_x,E_y) > k){// 如果最短距离大于k是肯定到不了的
			printf("NO\n");
			continue;
		}
		else{
			memset(vis,0,sizeof(vis));
			vis[S_x][S_y] = 1;
			dfs(S_x,S_y,0);
			if(flag)printf("YES\n");
			else printf("NO\n");
		}
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券