水管工游戏

 

本题依然是采用搜索，深搜，广搜都可以，本代码采用深搜，此题在搜索时需要增加一些判断条件以及下一步要搜索的位置即可。

代码如下：

#include
     
      int a[51][51];int book[51][51],n,m,flag=0,top=0;void dfs(int x,int y,int front); struct note{    int x;    int y;}s[100];int main(void){    int i,j,num=0;    scanf("%d%d",&n,&m);    for(i=1;i<=n;i++)    {        for(j=1;j<=m;j++)        {            scanf("%d",&a[i][j]);        }    }    dfs(1,1,1);    if(flag==0)    {        printf("impossible\n");    }    else    {        printf("\n");    }    return 0;}void dfs(int x,int y,int front)//front 的值为 1 ，2 ，3 ，4 分别表示进水口的位置在 左，上，右，下{    int i;        /* 测试当前栈内坐标 *///    for(i=1;i<=top;i++)//    {//        printf("(%d,%d)",s[i].x,s[i].y);//    }//    printf("\n");     if(x==n&&y==m+1) //此处的判定条件为 m+1     {        flag=1;        for(i=1;i<=top;i++)        {            printf("(%d,%d)",s[i].x,s[i].y);        }        return ;    }    if(x<1||x>n||y<1||y>m)    {        return ;    }    if(book[x][y]==1)    {        return ;    }    book[x][y]=1;        //将当前尝试坐标入栈     top++;    s[top].x=x;    s[top].y=y;        if(a[x][y]>=5&&a[x][y]<=6)//当前水管是直管的情况     {        if(front==1)        {            dfs(x,y+1,1);        }        if(front==2)        {            dfs(x+1,y,2);        }        if(front==3)        {            dfs(x,y-1,3);        }        if(front==4)        {            dfs(x-1,y,4);        }    }    if(a[x][y]>=1&&a[x][y]<=4)//当前水管是弯管的情况     {        if(front==1)        {            dfs(x+1,y,2);            dfs(x-1,y,4);        }        if(front==2)        {            dfs(x,y+1,1);            dfs(x,y-1,3);        }        if(front==3)        {            dfs(x-1,y,4);            dfs(x+1,y,2);        }        if(front==4)        {            dfs(x,y+1,1);            dfs(x,y-1,3);        }    }//    book[x][y]=0; // 本语句可将标记数组复原，本题中可有可无     top--; //将当前尝试坐标出栈     return ;    }