题目描述(ID:12023)

标题: 水管工游戏
详情:
这小节有点难，看不太懂可以跳过哦。
最近小哼又迷上一个叫做水管工的游戏。游戏的大致规则是这样的。一块矩形土地被分为N*M的单位正方形，现在这块土地上已经埋设有一些水管，水管将从坐标为(1,1)左上角左部边缘，延伸到(N,M)右下角右部边缘。水管只有2种，如下图所示。

每种管道将占据一个单位正方形土地。你现在可以旋转这些管道，使得构成一个管道系统，即创造一条从(1,1)到(N,M)的连通管道。标有树木的方格表示这里没有管道。如下图：一个4*5的土地中(4,2)处有一个树木。

我们可以旋转其中的一些管道，使之构成一个连通的管道系统，如下图。

如果通过旋转管道可以使之构成一个连通的管道系统，就输出铺设的路径，否则粗出impossible。

输入格式: 
输入的第一行为两个整数N和 M(都不超过10)，接下来的N行，每行有M个整数，表示地图中的每一小格。其中0表示树木，1~6分别表示管道的六种不同的摆放方式
样例:

输入

5 4
5 3 5 3
1 5 3 0
2 3 5 1
6 1 1 5
1 5 5 4

输出

(1,1) (1,2) (2,2) (3,2) (3,3) (3,4) (4,4) (5,4)

思路：

水管有六种，水管的来源方向有四种，所以还要分直管和弯管分情况讨论。。


代码：

#include<iostream>
#include<cstdio>  
using namespace std;
int a[51][51];  
int book[51][51];  
int n,m,flag=0;  
struct node  
{  
    int x;  
    int y;  
}s[100];  
int top=0;  
void dfs(int x,int y,int front)  
{  
    int i;  
    if(x==n&&y==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 ;  
}  
int main()  
{  
    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");  
    return 0;  
}