读书人

回溯有关问题

发布时间: 2012-03-21 13:33:15 作者: rapoo

求助:回溯问题
问题描述:笑笑最喜欢玩积木,每一次玩,她都会把积木在地上摊开,清点积木的个数。假设地面有一个10*10的网格,每个积木都由若干个正方形拼成。每一块地要么是空,要么被某个积木完全覆盖,可以保证,在地面上没有两块积木有公共边的情况,笑笑希望我们帮助编程求出:对给定的地面覆盖情况,共有多少块积木。
输入格式:一个10*10的0 1矩阵,1表示该单位正方形被某个积木覆盖,0表示没有覆盖
输出格式:一个整数,表示地面上共有的积木块数
样例输入:0 1 1 1 1 0 0 1 0 0
0 0 0 0 0 0 1 1 1 1
0 1 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 0 0
样例输出:8

#include<stdio.h>
int map[10][10]={0},v[10][10]={0};
int Q(int i,int j)
{if(i==9&&j==9)
return 1;
else
if(map[i][j]&&v[i][j]==0&&i>=0&&j>=0)
{v[i][j]=1;
Q(i+1,j);
Q(i,j+1);
Q(i-1,j);
Q(i,j-1);}
return 0; }

int main()
{int i,j,count=0;
for(i=0;i<10;i++)
for(j=0;j<10;j++)
scanf("%d",&map[i][j]);
i=0;j=0;
while(i<10)
{for(;i<10;i++)
{for(;j<10;j++)
if(map[i][j]&&v[i][j]==0)
count++;
Q(i,j);}
}
printf("%d",count);
while(1);}
程序运行中得不到正确的积木块数,求助大牛们如何修改????

[解决办法]
首先这个循环有问题
{for(;i<10;i++)
{for(;j<10;j++)
if(map[i][j]&&v[i][j]==0)
count++;
Q(i,j);}
}
内层循环的j只初始化了一次,也就是说,当内层循环第一次结束后,j的值一直是10
正确的代码是
{for(i=0;i<10;i++)
{for(j=0;j<10;j++)
if(map[i][j]&&v[i][j]==0)
count++;
Q(i,j);}
}

其次算法也有问题,修改上面的问题后,结果是16,正确的代码如下,仅供参考;
#include<stdio.h>
int map[10][10]= {0},v[10][10]= {0};
void Q(int i,int j)
{
if(i<0 || j<0 || i>9 || j>9)
{
return ;
}
if(map[i][j]&&v[i][j] == 0)
{
v[i][j]=1;
Q(i+1,j);
Q(i,j+1);
Q(i-1,j);
Q(i,j-1);
}
}

int main()
{
int i,j,count=0;
for(i=0; i<10; i++)
for(j=0; j<10; j++)
scanf("%d",&map[i][j]);

for(i = 0; i<10; i++)
{
for(j = 0; j<10; j++)
{
if(map[i][j] && v[i][j]==0)
{
count++;
Q(i,j);
}
}
}
printf("%d",count);
while(1);
}

读书人网 >C语言

热点推荐