admin 管理员组文章数量: 887021
java递归红与黑答案,递归
问题描述 (其实就是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
#include
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 #include 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; }
本文标签： java递归红与黑答案 递归
版权声明：本文标题：java递归红与黑答案,递归 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687924677h158097.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论