dfs的剪枝优化

两个剪枝问题

1. 当两点的距离（需要走的步数）大于剩下的时间时剪去

2.奇偶剪枝问题

如果起点到终点所需走的步数的奇偶性与时间奇偶性不同的时候剪去

起点到终点步数的奇偶性的判断

首先明确点的奇偶性判断看起横纵坐标和为奇数还是偶数

如果起点和终点的奇偶性相同则步数为偶数否则为奇数

具体的代码实现 (start1+start2+end1+end2+time)%2==1 (如果两个数的奇偶性相同的话两者和对2取余为0)

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
int n,m,time;
int flag;//判断是否有符合条件的搜索
int visit[20][20];
char mapp[20][20];
int dir[4][2]={{0,1},{0,-1},{-1,0},{1,0}};//用于四个方向的遍历
void dfs(int x,int y,int t)
{
int i;
if(flag==1) return;//找到一个就退回。。减少时间的消耗
if(mapp[x][y]=='D')
{
    if(t==time)
    flag=1;
    return; //递归的终止条件得多注意
    }
if(t>=time) return;
for(i=0;i<4;i++)
{
int xx,yy;
xx=x+dir[i][0];
yy=y+dir[i][1];
if(xx<0||xx>=n||yy<0||yy>=m||mapp[xx][yy]=='X'||visit[xx][yy]==1) continue;
visit[xx][yy]=1;
dfs(xx,yy,t+1);//此时的i如果为全局变量的话这里就对i的值做了改变
visit[xx][yy]=0;
}
}

int main()
{
   int start1,start2,i,j,end1,end2;
   while(scanf("%d %d %d",&n,&m,&time)!=EOF)
{
    if(n==0&&m==0&&time==0) break;
   memset(visit,0,sizeof(visit));
   flag=0;
   for(i=0;i<n;i++)
   {
    for(j=0;j<m;j++)
    {
       cin>>mapp[i][j];
    }
   }
   for(i=0;i<n;i++)//找到初始位置终止位置便于剪枝的进行
   {
    for(j=0;j<m;j++)
    {
     if(mapp[i][j]=='S')
     {
      start1=i;
      start2=j;
     }
     if(mapp[i][j]=='D')
{
   end1=i;
end2=j;
}
    }
   }
   if((abs(start1-end1)+abs(start2-end2))>time||(start1+start2+end1+end2+time)%2==1)//剪枝咯第一个剪枝为如果剩下的距离大于时间剪去第二个剪枝是奇偶减枝
   {
printf("NO\n");
continue;
   }
   visit[start1][start2]=1;
   dfs(start1,start2,0);
   if(flag==1) printf("YES\n");
   else printf("NO\n");
}
return 0;
}

这次优化主要就是应用了剪枝加油

巴特西

dfs的剪枝优化

最新文章

热门文章