首页 > 代码库 > HDU 1241 Oil Deposits(dfs)

HDU 1241 Oil Deposits(dfs)

技术分享
#include<cstdio>#include<cmath>#include<cstring>#include<iostream>#include<algorithm>using namespace std;char mat[10][10];int vis[10][10];int ok,dx,dy;int m,n,d;int op[4][2]={0,1,1,0,0,-1,-1,0};bool jiezhi(int x,int y,int rt){  int now=abs(dx-x)+abs(dy-y);  if(d-rt<now) return false;  if((d-rt-now)%2!=0) return true;  return true;}bool okn(int x,int y,int rt){  if(x<0||x>=n||y<0||y>=m||rt>d||vis[x][y]==1||mat[x][y]==X) return false;  if(rt<d&&mat[x][y]==D) return false;  if(rt==d)  {    if(mat[x][y]==D) ok=1;    return false;  }  return true;}void dfs(int x,int y,int rt){  if(jiezhi(x,y,rt)!=1||ok) return;  int nx,ny;  for(int i=0;i<4;i++)  {    nx=x+op[i][0];    ny=y+op[i][1];    if(okn(nx,ny,rt+1))    {      vis[nx][ny]=1;      dfs(nx,ny,rt+1);      vis[nx][ny]=0;    }  }}int main(){  int i,j,k;  int sx,sy;    while(scanf("%d%d%d",&n,&m,&d)!=EOF)    {        if(n==0||m==0||d==0) break;        ok=0;        for(i=0; i<n; i++)        {            scanf("%s",mat[i]);        }        memset(vis,0,sizeof(vis));        for(i=0; i<n; i++)            for(j=0; j<m; j++)                {                  if(mat[i][j]==S)                  {                    sx=i;                    sy=j;                  }                  else if(mat[i][j]==D)                  {                    dx=i;dy=j;                  }                }        if(jiezhi(sx,sy,0))        {          vis[sx][sy]=1;          dfs(sx,sy,0);        }        if(ok) printf("YES\n");        else printf("NO\n");    }  return 0;}
View Code

 

HDU 1241 Oil Deposits(dfs)