递归–红与黑

问题描述 （其实就是POJ的1979，那上面的测试数据更多）

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一

块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多

少块黑色的瓷砖。

输入数据

包括多个数据集合。每个数据集合的第一行是两个整数W 和H，分别表示x 方向

和y 方向瓷砖的数量。W 和H 都不超过20。在接下来的H 行中，每行包括W 个字符。

每个字符表示一块瓷砖的颜色，规则如下

1）‘.’：黑色的瓷砖；

2）‘#’：白色的瓷砖；

3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一

次。

当在一行中读入的是两个零时，表示输入结束。

输出要求

对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时

包括初始位置的瓷砖)。

输入样例

6 9

....#.

.....#

......

......

......

......

......

#@...#

.#..#.

0 0

我的思路：每个点都有四个方向可以走，那么就往四个方向递归呗。f(x,y)=f(x-1，y)+f(x+1,y)+f(x,y-1)+f(x,y+1)，然后把每个走过的点做标记。但是出口的条件是什么？？不知道！！思考了半天想不出来。其实很简单！没走过一点就加个一！！这个是关键！！ 出口就是当出界或者遇到红色的。 我的方法是建立个int型二位数组与之对应，其实是多此一举，只需要用一个char型数组就OK了。

下面是我的程序：

#include <stdio.h>
#include <stdlib.h>

int arr[20][20];
int w,h;


int step(int x, int y)
{
    if(x>=h || x<0 || y>=w || y<0 || arr[x][y]==1)
    {
        return 0;
    }
    else if(arr[x][y] == 0)
    {
        arr[x][y]=1;
        return 1+step(x+1,y)+step(x-1,y)+
            +step(x,y+1)+step(x,y-1);
    }
}

void printArr(int x,int y)
{
    int r,c;
    for(r = 0; r < x; r++)
    {
        for(c = 0; c < y; c++)
        {
            printf("%d",arr[r][c]);
        }
        printf("\n");
    }
}

int main()
{
    int r,c;
    int px,py;  //start position
    int nCount;
    char szStr[21];
    //FILE *fp;
    //fp=fopen("in.txt","r");


    while(scanf("%d%d",&w,&h) && w!=0 && h!=0)
    {
        memset(arr,0,sizeof(arr));

        for(r = 0; r < h; r++)
        {
            //fscanf(fp,"%s",&szStr);
            scanf("%s",&szStr);
            for(c = 0; c < w; c++)
            {
                if(szStr[c] == '.')
                {
                    arr[r][c]=0;
                }
                else if(szStr[c] == '#')
                {
                    arr[r][c]=1;
                }
                else
                {
                    px=r;py=c;
                }
            }
        }//for

        nCount=step(px,py);

        //printArr(h,w);
        printf("%d\n",nCount);
    }    
    return 0;
}2013/5/17

修改后的程序：

#include <stdio.h>
#include <stdlib.h>

char szArr[21][21];
int w,h;

int step(int x, int y)
{
    if(x>=h || x<0 || y>=w || y<0 || szArr[x][y] == '#')
    {
        return 0;
    }
    else if(szArr[x][y] == '.' || szArr[x][y] == '@')
    {
        szArr[x][y]='#';
        return 1+step(x+1,y)+step(x-1,y)+
            +step(x,y+1)+step(x,y-1);
    }
}

int main()
{
    int r,c;
    int px,py;  //start position
    int nCount;
    //FILE *fp;
    //fp=fopen("in.txt","r");


    while(scanf("%d%d",&w,&h) && w!=0 && h!=0)
    {    
        for(r = 0; r < h; r++)
        {
            //fscanf(fp,"%s",szArr[r]);
            scanf("%s",szArr[r]);
            for(c = 0; c < w; c++)
            {
                if(szArr[r][c] == '@')
                {
                    px=r;py=c;
                }
            }
        }

        nCount=step(px,py);
        printf("%d\n",nCount);
    }

    return 0;
}

原文链接: https://www.cnblogs.com/Jason-Damon/archive/2013/05/17/3084465.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍