首页 > 代码库 > HDU_1175_dfs

HDU_1175_dfs

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

 

dfs(x,y,i,num),xy表示位置,i表示方向,num表示转向次数,num=2时候的剪枝很重要。

 

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int a[1005][1005],vis[1005][1005],n,m,endx,endy,dis[4][2] = {{-1,0},{0,-1},{1,0},{0,1}},flag;void dfs(int x,int y,int dir,int num){    if(flag)    return;    if(x == endx && y == endy)    {        flag = 1;        return;    }    if(num == 2)    {        if(dir == 0||dir == 2)        {            if(y != endy)   return;        }        else        {            if(x != endx)   return;        }    }    int xx,yy;    for(int i = 0;i < 4;i++)    {        xx = x+dis[i][0];        yy = y+dis[i][1];        if(xx < 1 || xx > n || yy < 1 || yy > m || vis[xx][yy])  continue;        if(xx == endx && yy == endy || a[xx][yy] == 0)        {            vis[xx][yy] = 1;            if(i == dir)    dfs(xx,yy,dir,num);            else if(num < 2)dfs(xx,yy,i,num+1);            vis[xx][yy] = 0;        }    }}int main(){    while(cin >> n >> m && n &&m)    {        flag = 0;        for(int i = 1;i <= n;i++)        {            for(int j = 1;j <= m;j++)   cin >> a[i][j];        }        int num;        cin >> num;        while(num--)        {            int beginx,beginy;            cin >> beginx >> beginy >> endx >> endy;            if(beginx == endx && beginy == endy || a[beginx][beginy] != a[endx][endy] || a[beginx][beginy] == 0)            {                cout << "NO" << endl;                continue;            }            flag = 0;            memset(vis,0,sizeof(vis));            for(int i = 0;i < 4;i++)            {                if(!flag)   dfs(beginx,beginy,i,0);            }            if(flag)    cout << "YES" << endl;            else    cout << "NO" << endl;        }    }    return 0;}

 

HDU_1175_dfs