Problem ID:1016 Red and Black
简单题意:给出一个地图,其中有一个起始点,标记为"."的地方可以走,为"#"的不能走。只能直走,不能斜向前进。求能到达的所有地区数。
解题思路形成过程:利用DFS,找出能到达的所有"."地区,每找到一个进行标记,从而剪枝、减少重复计算。
因此,此题递归共有3个条件:①:所遍历到的行、列不能超出地图范围;
②:所遍历到的地区必须为"."标记;
③:此地区在之前的遍历过程中没有没标记过;
感想: 注意细节,因为一个变量名输错了,导致编译没错但是运行结果有错,找了好久才发现。
注意初始时输入的行数和列数的顺序。
代码:
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int cmap[21][21];
bool mark[21][21];
int dir[4][2]={{-1,0},{0,-1},{0,1},{1,0}};//上、左、右、下
int w,h;
int dfs(int r,int c)
{
int num=1;
for(int i=0;i<4;++i)
{
int temp_r=r;
int temp_c=c;
temp_r+=dir[i][0];
temp_c+=dir[i][1];
if(temp_r>=0&&temp_r<h&&temp_c>=0&&temp_c<w){
if(cmap[temp_r][temp_c]==2&&mark[temp_r][temp_c]==false){
mark[temp_r][temp_c]=true;
num+=dfs(temp_r,temp_c);
}
}
}
return num;
}
int main()
{
freopen("1.txt","r",stdin);
while(scanf("%d%d",&w,&h)!=EOF)
{
if(w==0)
return 0;
memset(mark,false,sizeof(mark));
int r_s,c_s;
for(int i=0;i<h;++i)
for(int j=0;j<w;++j){
char temp;
cin>>temp; //如果用scanf("%c",&temp);会出现错误,需要考虑输入中的回车问题。
if(temp=='@'){
cmap[i][j]=1;
r_s=i;
c_s=j;
}
else if(temp=='.')
cmap[i][j]=2;
else if(temp=='#')//此条件语句可不写。
cmap[i][j]=3;
}
mark[r_s][c_s]=true;
int cnt=dfs(r_s,c_s);
printf("%d\n",cnt);
}
}