2 hjw1012703395 hjw1012703395 于 2016.09.12 21:39 提问

啊哈!算法水管工游戏为什么要取消标记

为什么要取消标记????
递归函数中return;是直接跳出整体函数,还是跳出当前函数回到上一层dfs所在位置继续进行之后的代码啊????

#include
#include
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(xn || ym)
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
*/

1个回答

devmiao
devmiao   Ds   Rxr 2016.09.12 23:58
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!