水管工游戏 （深搜）

水管工游戏

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

代码如下：

#include<stdio.h>
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 ;    
}