poj－1979改－红与黑

今天凌晨五点拿到一道很有意思的题，做了好大会才做了出来，发现每一道竞赛题的题目都十分值得斟酌，有些话读一两遍根本无法深入了解其中的奥妙，它的要求有时候与我们的第一感觉完全不一样，所以需要我们好好的多读几遍，细细的体会其中的隐藏的条件……我称其为潘多拉之谜，只要注意到了这个，往往会事半功倍，因为有的时候我们往往不是因为核心代码被pass了，而是我们的细节没有按照题意而导致失败！
好了，废话说完，看题：

问题描述：
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖，你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请你写出一个程序，计算你总共能达到多少块黑色瓷砖。
输入数据：
包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别代表x方向和y方向瓷砖的数量。W和H都不超过20.接下来的H行中，每行包括W各字符。每个字符表示一块瓷砖的颜色，规则如下：
‘$’：黑色的瓷砖
‘#’：白色的瓷砖
‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集上唯一出现一次。
当在一行读出的两个零时，表示输入结束。
输出要求：
对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数（计数时包括初始位置时的瓷砖）。
输入样例：
6 9

$$$$#$
$$$$$#
$$$$$$
$$$$$$
$$$$$$
$$$$$$
$$$$$$
#@$$$#
$#$$#$

0 0
输出样例：
45
最初我一下子就有了思路，虽然后来证明我的思路是错我的，但是一开始我还是鄙视了这道题五分钟，当我知道自己搞错了后，我又鄙视了自己五分钟，为我的冒失付出代价，有的时候真的不能得意忘形，很容易自己就走进了自己得意的误区。一开始我把这道题想成了一道类似于迷宫的题，我想可以以右为尊，挨着右边的去过一遍这个房子，但是后来我发现这样子并不能遍历所有的黑瓷砖，当我认识到这一点后，很顺其自然的将这个题改成了深度搜索的方法，然后再加以修改细节的问题，这道题就解决了。代码如下：

#include <stdio.h>
int K;
char FangZi[20][20]={''};
void KS(int i,int j,int W,int H)
{
FangZi[i][j]='#';
if (j<(W-1)&&FangZi[i][j+1]=='$')
{
K++;
KS(i, j+1, W, H);
}
if (j>0&&FangZi[i][j-1]=='$')
{
K++;
KS(i, j-1, W, H);
}
if (i<(H-1)&&FangZi[i+1][j]=='$')
{
K++;
KS(i+1, j, W, H);
}
if (i>0&&FangZi[i-1][j]=='$')
{
K++;
KS(i-1, j, W, H);
}
return ;
}
int main(int argc, const char * argv[])
{
int W=0,H=0,i=0,j=0,k=0,KuaiShu[20];
while (scanf("%d %d",&W,&H))
{
if (W==0&&H==0)
{
break;
}
for (i=0; i<H; i++)
{
scanf("%s",FangZi[i]);
}
for (i=0; i<H; i++)
{
for (j=0; j<W; j++)
{
if (FangZi[i][j]=='@')
{
K=1;
KS(i, j, W, H);
KuaiShu[k]=K;
}
}
}
k++;
}
for (i=0; i<k; i++)
{
printf("%dn",KuaiShu[i]);
}
return 0;
}

主体就是一个主函数加一个深度搜索的递归函数，代码略显多，但是方法很简单，值得提醒的是，调用的递归函数中的每一个将'@'或'$'变成'＃'的过程都要写在递归函数的主体内，不能写在每一个if语句内，因为一旦写在里面，而外面不写，那么就会出错，会莫明其妙的有几个位置重复调用覆盖，使结果比实际的要多。这个问题是我一时的疏忽发现的，虽然具体的错误的原因我并不懂，但是值得以后注意，并且这样子写在主体中的话，函数也会相对简洁，实为一举两得之举，所以要时刻提醒自己，有的时候越是简洁的，越是正确的！哦啦(☆_☆)……

最后

以上就是务实巨人为你收集整理的poj－1979改－红与黑的全部内容，希望文章能够帮你解决poj－1979改－红与黑所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。