啊哈！算法里的水管工游戏问题
为什么要取消标记？？？？递归函数中return；是直接跳出整体函数，还是跳出当前函数回到上一层dfs所在位置继续进行之后的代码啊？？？？
#include <stdio.h>
#include <stdlib.h>
int a[51][51];
int book[51][51],n,m,flag=0;
struct note
{
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");
else
printf("找到铺设方案\n");
return 0;
}
/*
5 4
5 3 5 3
1 5 3 0
2 3 5 1
6 1 1 5
1 5 5 4
*/
