首页 > 代码库 > zoj2110深搜

zoj2110深搜

#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;int dx[4]={0,-1,0,1};int dy[4]={-1,0,1,0};int Map[10][10];int vis[10][10];int n,m,k;int flag=0;int bs,be,es,ee;int Abs(int a){    return a>0?a:-a;}void dfs(int x,int y,int t){    cout<<x<<" "<<y<<endl;system("pause");    int cc=Abs(x-es)+Abs(y-ee);    int kk=k-t-cc;    if(kk<0||kk%2) return ;    if(flag) return ;    if(x==es&&y==ee){        if(t==k){            flag=1;return ;        }    }    for(int i=0;i<4;i++){        int xx=dx[i]+x;int yy=dy[i]+y;        if(xx>=0&&xx<n&&yy>=0&&yy<m&&!vis[xx][yy]&&Map[xx][yy]){            vis[xx][yy]=1; t++;            dfs(xx,yy,t);            vis[xx][yy]=0;t--;        }    }}int main(){    while(cin>>n>>m>>k,n||m||k){        flag=0;        getchar();        memset(vis,0,sizeof(vis));        memset(Map,0,sizeof(Map));        for(int i=0;i<n;i++){            for(int j=0;j<m;j++){                char c;cin>>c;                if(c==‘S‘){                    bs=i;be=j;Map[i][j]=0;                }                if(c==‘D‘){                    es=i;ee=j;Map[i][j]=1;                }                if(c==‘.‘){                    Map[i][j]=1;                }                if(c==‘X‘){                    Map[i][j]=0;                }            }            getchar();        }        dfs(bs,be,0);        if(flag) cout<<"YES"<<endl;        else cout<<"NO"<<endl;    }    return 0;}