hooj 1010 经典深搜

川长思鸟来 2022-11-20 04:56 103阅读 0赞

c++能过。。。。c语言的话就一直wa 求解

#include<iostream>
    #include<cmath>
    #include<cstring>
    #include<queue>
    int fangxiang[4][2]={
      {-1,0},{1,0},{0,-1},{0,1}};
    const int MAX=101;
    char map[MAX][MAX];
    int mark[MAX][MAX];
    int  n,m,t;
    int start_x,start_y;
    int end_x,end_y;
    using namespace std;
    bool DFS(int x,int y,int step)
    {
    	int i,a,b;
    	if(map[x][y]=='D'&&step==t)
    	return true;
    	if(x<1||x>n|y<1||y>m)
    	return false;
    	if(step>=t)//剪枝1：当step>=T时还没有找到D点 
    	return false;
    	if(t-step<(abs(x-end_x)+abs(y-end_y)))//剪枝2：还需要的步数比理论上的最短距离还小  
    	return false;
    	if((t-step-(abs(x-end_x)+abs(y-end_y)))%2!=0) //剪枝3：比理论上的最短距离多出来的必是偶数 
    	return false;
    	for(i=0;i<4;i++)
    	{
    		a=x+fangxiang[i][0];
    		b=y+fangxiang[i][1];
    		if(a<=n&&a>=1&&b>=1&&b<=m&&map[a][b]!='X'&&!mark[a][b]) //判断三个条件：1.检验_x,_y是否越界。2.看vis[][]是否访问过。3.看map[][]是否是墙 
    		{
    			mark[a][b]=1;
    			if(DFS(a,b,step+1))
    			return true;
    			else
    			mark[a][b]=0;
    		}
    	}
    	return false;
    }
    int main()
    {
    	int i,j;
    	while(cin>>n>>m>>t&&(n||m||t))
    	{
    		memset(mark,0,sizeof(mark));
    		for(i=1;i<=n;i++)
    		{
    			for(j=1;j<=m;j++)
    			{
    			 	cin>>map[i][j];
    			 	if(map[i][j]=='S')
    			 	{
     					start_x=i;
     					start_y=j;
     				}
     				if(map[i][j]=='D')
     				{
    				 	end_x=i;
    					end_y=j;	
    		 		}
    			}
    		}
    		mark[start_x][start_y]=1;
    		if(DFS(start_x,start_y,0))
    		cout<<"YES"<<endl;
    		else
    		cout<<"NO"<<endl;
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，103人围观）

还没有评论，来说两句吧...

相关阅读

相关广搜与深搜

一、深搜属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次；

绝地灬酷狼/ 2024年01月08日 13:19/ 0 赞/ 55 阅读

相关 leetcode 子集深搜

一(每一个数选或不选 > 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 > 说明：解集不能包含重复的子集。 > 示例: > 输入:

Dear 丶/ 2023年08月17日 15:43/ 0 赞/ 101 阅读

相关 hooj 1010 经典深搜

c++能过。。。。c语言的话就一直wa 求解 include<iostream> include<cmath> include<cstring

川长思鸟来/ 2022年11月20日 04:56/ 0 赞/ 104 阅读

相关素数环（深搜）

描述有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的

亦凉/ 2022年09月28日 13:01/ 0 赞/ 155 阅读

相关经典搜索（深搜+剪枝+Java细节注意）

Tempter of the Bone Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768

你的名字/ 2022年08月20日 13:24/ 0 赞/ 135 阅读

相关深搜和广搜（初学者）

搜索入门最近对搜索有了一点浅显的了解，想跟大家分享分享。说起来我也是初学者，恰巧有些自己的理解，想起来自己开始学习搜索的情况，真是一把鼻子一把

淩亂°似流年/ 2022年06月08日 09:08/ 0 赞/ 296 阅读

相关 Rescue-HDU-深搜

Rescue Problem Description Angel was caught by the MOLIGPY! He was put in pri

╰半橙微兮°/ 2022年06月05日 06:26/ 0 赞/ 210 阅读

相关【深搜】单词方阵

声明 -------------------- 我的码风可能有点和别人不太一样（其实就是有点奇怪），大家重在意会即可。 [原题传送门][Link 1] 前言

叁歲伎倆/ 2021年12月24日 08:31/ 0 赞/ 260 阅读

相关算法——广搜(BFS)/深搜(DFS)

在图的基本算法中，最初接触的就是图的遍历算法，根据访问节点的顺序，可分为广度优先搜索（`BFS`）和深度优先搜索（`DFS`）。广度优先搜索广度优先搜索算法

今天药忘吃喽~/ 2021年11月05日 07:04/ 0 赞/ 475 阅读

相关 HDU 1010 - Tempter of the Bone（深搜+奇偶剪枝）

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1010][http_acm.hdu.edu.cn_showproblem.p

朴灿烈づ我的快乐病毒、/ 2021年09月26日 07:46/ 0 赞/ 265 阅读