問題描述?（其實(shí)就是POJ的1979，那上面的測(cè)試數(shù)據(jù)更多）
有一間長(zhǎng)方形的房子，地上鋪了紅色、黑色兩種顏色的正方形瓷磚。你站在其中一
塊黑色的瓷磚上，只能向相鄰的黑色瓷磚移動(dòng)。請(qǐng)寫一個(gè)程序，計(jì)算你總共能夠到達(dá)多
少塊黑色的瓷磚。
輸入數(shù)據(jù)
包括多個(gè)數(shù)據(jù)集合。每個(gè)數(shù)據(jù)集合的第一行是兩個(gè)整數(shù)W 和H，分別表示x 方向
和y 方向瓷磚的數(shù)量。W 和H 都不超過20。在接下來的H 行中，每行包括W 個(gè)字符。
每個(gè)字符表示一塊瓷磚的顏色，規(guī)則如下
1）‘.’：黑色的瓷磚；
2）‘#’：白色的瓷磚；
3）‘@’：黑色的瓷磚，并且你站在這塊瓷磚上。該字符在每個(gè)數(shù)據(jù)集合中唯一出現(xiàn)一
次。
當(dāng)在一行中讀入的是兩個(gè)零時(shí)，表示輸入結(jié)束。
輸出要求
對(duì)每個(gè)數(shù)據(jù)集合，分別輸出一行，顯示你從初始位置出發(fā)能到達(dá)的瓷磚數(shù)(記數(shù)時(shí)
包括初始位置的瓷磚)。
輸入樣例

6 9
....#.
.....#
......
......
......

......
......
#@...#
.#..#.
0 0

我的思路：每個(gè)點(diǎn)都有四個(gè)方向可以走，那么就往四個(gè)方向遞歸唄。f(x,y)=f(x-1，y)+f(x+1,y)+f(x,y-1)+f(x,y+1)，然后把每個(gè)走過的點(diǎn)做標(biāo)記。但是出口的條件是什么？？不知道！！思考了半天想不出來。其實(shí)很簡(jiǎn)單！沒走過一點(diǎn)就加個(gè)一！！這個(gè)是關(guān)鍵！！?? 出口就是當(dāng)出界或者遇到紅色的。 我的方法是建立個(gè)int型二位數(shù)組與之對(duì)應(yīng)，其實(shí)是多此一舉，只需要用一個(gè)char型數(shù)組就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;
}
/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;
}

總結(jié)

以上是生活随笔為你收集整理的递归--红与黑的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。