首页 > 代码库 > HOJ 1797 Red and Black
HOJ 1797 Red and Black
传送门 http://acm.hit.edu.cn/hoj/problem/view?id=1797
总体的思路是遍历可以到达的‘ . ‘,将其对应的vis数组化为1,然后统计所有为1的vis项;
①常用的加边法,防止越界
②初始化,不然两次相同的输入得到的结果会不同,由于是二维数组,能力有限,只好在结尾初始化,为下次输入做准备
③结束条件,递归函数一定要先写好结束条件,不然会炸
④上下左右四向移动
⑤直接递归函数调用自身
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 char str[30][30]; 5 char s[100]; 6 int vis[30][30]; 7 int dx[4]= {-1,0,1,0}; 8 int dy[4]= {0,1,0,-1}; 9 int dfs(int x,int y) 10 { 11 int next_x,next_y,k; 12 if(str[x][y]==‘#‘||vis[x][y]||str[x][y]==0) //③ 13 return 0; 14 vis[x][y]=1; 15 for(k=0; k<4; k++) // ④ 16 { 17 next_x=x+dx[k]; 18 next_y=y+dy[k]; 19 if(dfs(next_x,next_y)) // ⑤ 20 return 1; 21 } 22 return 0; 23 } 24 int main() 25 { 26 int w,h,i,j,startx,starty,ans; 27 while(scanf("%d %d",&w,&h)!=EOF) 28 { 29 ans=0; 30 if(w==0&&h==0) 31 break; 32 for(i=1; i<=h; i++) // ① 33 { 34 scanf("%s",s); 35 for(j=1; j<=w; j++) 36 { 37 str[i][j]=s[j-1]; 38 } 39 } 40 for(i=1; i<=h; i++) 41 { 42 for(j=1; j<=w; j++) 43 { 44 vis[i][j]=0; 45 if(str[i][j]==‘@‘) 46 { 47 startx=i; 48 starty=j; 49 break; 50 } 51 } 52 } 53 dfs(startx,starty); 54 for(i=1;i<=h;i++) 55 { 56 for(j=1;j<=w;j++) 57 { 58 //printf("%d ",vis[i][j]); 59 if(vis[i][j]==1) 60 ans++; 61 } 62 //puts(""); 63 } 64 for(i=0;i<=h;i++) // ② 65 { 66 for(j=0;j<=w;j++) 67 { 68 str[i][j]=0; 69 vis[i][j]=0; 70 } 71 } 72 printf("%d\n",ans); 73 } 74 return 0; 75 }
HOJ 1797 Red and Black
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。