注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1010  

2012-03-16 14:03:15|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://acm.hdu.edu.cn/showproblem.php?pid=1010

DFS,注意剪枝

题意:给出一个矩阵,'S'表示起点,'D'表示终点,'X'表示墙,只能上下左右4个方向走,每走一步为1秒,给你一个时间Time,问能否用Time时间走到终点

AC Code:

#include<iostream>
#include<string.h>
#include<math.h>
#include<queue>
#include<string>
#include<algorithm>
#include<stdio.h>
using namespace std;
int n,m,Time,flag;
int s_x,s_y,e_x,e_y;
int dir[4][2]={-1,0,1,0,0,-1,0,1};
char map[10][10];

void DFS(int x,int y,int t)
{
 int i,x1,y1;
 if(flag)
  return ;
 if(x==e_x && y==e_y && t==Time)
 {
  flag=1;
  return ;
 }
 if((Time-t)%2 != (abs(x-e_x)+abs(y-e_y))%2)  //奇偶减枝法
  return ;
 if(abs(x-e_x)+abs(y-e_y) > Time-t)   //当前点到终点的最短时间若比剩余的时间还长的话
  return;
 for(i=0;i<4;i++)
 {
  x1=x+dir[i][0];
  y1=y+dir[i][1];
  if(x1<n && x1>=0 && y1<m && y1>=0 && map[x1][y1]!='X')
  {
   map[x1][y1]='X';
   t++;
   DFS(x1,y1,t);
   t--;
   map[x1][y1]='.';
  }
 }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("testin.txt","r",stdin);
#endif
 int i,j,count;
 while(scanf("%d %d %d",&n,&m,&Time)!=EOF)
 {
  if(!n && !m && !Time)
   break;
  flag=0;count=0;
  for(i=0;i<n;i++)
   for(j=0;j<m;j++)
   {
    cin>>map[i][j];
    if(map[i][j]=='S')
    {
     s_x=i;
     s_y=j;
     map[i][j]='X';  //将起点修改为以访问
    }
    else if(map[i][j]=='.')
     count++;
    else if(map[i][j]=='D')
    {
     e_x=i;
     e_y=j;
    }
   }
  if(count+1<Time)  //总共可以走的步数如果比给定时间还少
  {
   printf("NO\n");
   continue;
  }
  DFS(s_x,s_y,0);
  if(flag)
   printf("YES\n");
  else
   printf("NO\n");
 }
    return 0;
}

 

奇偶剪枝法:

http://baike.baidu.com/view/7789287.htm

  评论这张
 
阅读(977)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018