No.4.6 水管拼接游戏

问题什么的就不介绍了，<<啊哈！算法>>第四章 第六节

一、先用广度优先算法

#include

// x,y表示格子的坐标，a[x][y]表示格子使用的水管型号1~6，0表示树木，进水口左上右下分别用1,2,3,4表示
int a[10][10],book[10][10]={0};
int n,m,flag=0;
struct node {　　//记录路径
　　int p;
　　int q;
};
struct node s[100];　　//stack
int top=0;　　　　　　//stack

/*queue module

struct node que[100];
int head=1,tail=1;

*/
void dfs(int x,int y,int front){
　　int i;
　　if(x==n && y==m+1){　　//为何必须是m+1，而不是m？！！
　　　　flag=1;

　　　　for(i=0;i 　　　　　　printf("(%d,%d)\t",s[i].p,s[i].q);　　//stack 遍历
　　　　}

　　　　/*

　　　　while(head

　　　　　　printf("(%d, %d)\t",que[head].p,que[head].q);
　　　　　　head++;
　　　　}

　　　　*/
　　　　return;　　//这个千万不能忘！
　　}
　　if(x<1 || x>n ||y<1 ||y>m)
　　　　return;
　　if (book[x][y]==1)
　　　　return;

　　book[x][y]=1;
　　s[top].p=x;
　　s[top].q=y;
　　top++;

　　/*　

　　que[tail].p=x;　　//这里一定是要操作tail指针，想想为什么！
　　que[tail].q=y;
　　tail++;

　　*/

　　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,4);
　　　　　　dfs(x+1,y,2);
　　　　}
　　　　if(front==2){
　　　　　　dfs(x,y-1,3);
　　　　　　dfs(x,y+1,1);
　　　　}
　　　　if(front==3){
　　　　　　dfs(x-1,y,4);
　　　　　　dfs(x+1,y,2);
　　　　}
　　　　if(front==4){
　　　　　　dfs(x,y-1,3);
　　　　　　dfs(x,y+1,1);
　　　　}
　　}

　　book[x][y]=0;　　//如果不满足if条件，退栈，并返回前一路经，继续尝试
　　top--;

　　/*　　tail--;　　*/
　　return;
}

int main(){
　　int i,j,front;
　　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("\nimpossible\n");
　　else
　　　　printf("\npossible\n");

　　getchar();getchar();
　　return 0;
}

二、深度优先算法

int a[10][10],book[10][10]={0};
int n,m,flag=0;
struct node {
　　int p;
　　int q;
};
struct node que[100];
int head=1,tail=1;

void dfs(int x,int y,int front){　　//逻辑判断都在DFS里面进行
　　int i;
　　if(x==n && y==m+1){
　　　　flag=1;
　　　　while(head 　　　　　　printf("(%d, %d)\t",que[head].p,que[head].q);
　　　　　　head++;
　　　　}
　　　　return;　　//这里return很重要，不然就会进入无限死循环
　　}
　　if(x<1 || x>n ||y<1 ||y>m)
　　　　return;
　　if (book[x][y]==1)
　　　　return;

　　book[x][y]=1;
　　que[tail].p=x;　　//养成在tail操作的习惯，除非head/tail -> queue你已经大圆满，时刻清楚知道head、tail指向位置及其值
　　que[tail].q=y;
　　tail++;
　　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,4);
　　　　　　dfs(x+1,y,2);
　　　　}
　　　　if(front==2){
　　　　　　dfs(x,y-1,3);
　　　　　　dfs(x,y+1,1);
　　　　}
　　　　if(front==3){
　　　　　　dfs(x-1,y,4);
　　　　　　dfs(x+1,y,2);
　　　　}
　　　　if(front==4){
　　　　　　dfs(x,y-1,3);
　　　　　　dfs(x,y+1,1);
　　　　}
　　}
　　book[x][y]=0;
　　tail--;
　　return;
}

int main(){
　　int i,j,front;
　　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("\nthat is impossible\n");
　　else
　　　　printf("\nit is possible\n");

　　getchar();getchar();
　　return 0;
}