封闭村庄改建(C/Py/Java/Js/Go)题解华为笔试真题 9月2号 第一题 100分题型题目内容王国规划官要统计一张地图上有多少个村庄之后会被改建成城墙。地图是hhh行www列的方格。每个格子不是城墙WWW就是村庄VVV。王国有两条规矩某一片村庄若被城墙完全围住沿村庄格子怎样走都到不了地图边界这块地就是封闭领地里面的村庄全部改成WWW。一个村庄若能沿着上下左右相邻的村庄走到地图最外一圈就算自由村庄可以和外界贸易不能改建。请根据给定地图求出会被改建成城墙的村庄个数。约束条件1≤h,w≤2001 \le h,w \le 2001≤h,w≤200地图只由字符WWW和VVV组成输入描述第一行两个整数hhh、www表示行数和列数。接下来hhh行每行一个长度为www的字符串描述这一行的地图。输出描述输出一个整数即会被改建成城墙的村庄个数。样例1输入2 2 WW WW输出0说明地图上没有村庄不需要改建答案为000。样例2输入3 5 WWWWW WVVVW WWWWW输出3说明中间一行的三个VVV四周都是城墙走不到边界三个村庄都要改建。样例3输入5 5 WWWWW WVWWW WVWVW WWVVW WWWWW输出5说明图中五个VVV都在内部彼此四连通且到不了边界全部改建。题解和思路思路实现思路DFS本题本质是城墙将不同村庄分割不同村庄连通块。求的是不与外界相邻连通块的村庄数量之和。求每个村庄连通块村庄数量可以通过DFS实现为了判断是否于外界相邻通过一个标志记录即可。算法总体时间复杂度为O(hw)C#includebits/stdc.husingnamespacestd;boolfound;inth,w;intdfs(vectorvectorchargrid,intx,inty){intdx[4]{-1,1,0,0};intdy[4]{0,0,-1,1};if(x0||xh-1||y0||yw-1){foundtrue;}intsum1;for(inti0;i4;i){intnxxdx[i];intnyydy[i];if(nx0||ny0||nxh||nyw||grid[nx][ny]W){continue;}// 去重grid[nx][ny]W;sumdfs(grid,nx,ny);}returnsum;}intmain(){cinhw;vectorvectorchargrid(h,vectorchar(w));for(inti0;ih;i){for(intj0;jw;j){cingrid[i][j];}}intans0;for(inti0;ih;i){for(intj0;jw;j){if(grid[i][j]V){foundfalse;grid[i][j]W;intsumdfs(grid,i,j);if(!found){anssum;}}}}coutans;return0;}Javaimportjava.io.*;importjava.util.*;publicclassMain{staticbooleanfound;staticinth,w;staticintdfs(char[][]grid,intx,inty){int[]dx{-1,1,0,0};int[]dy{0,0,-1,1};if(x0||xh-1||y0||yw-1){foundtrue;}intsum1;for(inti0;i4;i){intnxxdx[i];intnyydy[i];// 越界或已经访问if(nx0||ny0||nxh||nyw||grid[nx][ny]W){continue;}// 去重grid[nx][ny]W;sumdfs(grid,nx,ny);}returnsum;}publicstaticvoidmain(String[]args)throwsException{BufferedReaderbrnewBufferedReader(newInputStreamReader(System.in));StringTokenizerstnewStringTokenizer(br.readLine());hInteger.parseInt(st.nextToken());wInteger.parseInt(st.nextToken());char[][]gridnewchar[h][w];for(inti0;ih;i){grid[i]br.readLine().trim().toCharArray();}intans0;for(inti0;ih;i){for(intj0;jw;j){if(grid[i][j]V){foundfalse;grid[i][j]W;intsumdfs(grid,i,j);if(!found){anssum;}}}}System.out.println(ans);}}pythonimportsysinputsys.stdin.readline foundFalseh,w0,0defdfs(grid,x,y):globalfound dx[-1,1,0,0]dy[0,0,-1,1]ifx0orxh-1ory0oryw-1:foundTruesum_1foriinrange(4):nxxdx[i]nyydy[i]ifnx0orny0ornxhornyworgrid[nx][ny]W:continue# 去重grid[nx][ny]Wsum_dfs(grid,nx,ny)returnsum_ h,wmap(int,input().split())grid[]for_inrange(h):grid.append(list(input().strip()))ans0foriinrange(h):forjinrange(w):ifgrid[i][j]V:foundFalsegrid[i][j]Wsum_dfs(grid,i,j)ifnotfound:anssum_print(ans)Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});constlines[];rl.on(line,line{lines.push(line.trim());});rl.on(close,(){const[h,w]lines[0].split(/\s/).map(Number);constgrid[];for(leti0;ih;i){grid.push(lines[i1].split());}letfoundfalse;functiondfs(x,y){constdx[-1,1,0,0];constdy[0,0,-1,1];if(x0||xh-1||y0||yw-1){foundtrue;}letsum1;for(leti0;i4;i){constnxxdx[i];constnyydy[i];if(nx0||ny0||nxh||nyw||grid[nx][ny]W){continue;}// 去重grid[nx][ny]W;sumdfs(nx,ny);}returnsum;}letans0;for(leti0;ih;i){for(letj0;jw;j){if(grid[i][j]V){foundfalse;grid[i][j]W;constsumdfs(i,j);if(!found){anssum;}}}}console.log(ans);});Gopackagemainimport(bufiofmtos)varfoundboolvarh,wintfuncdfs(grid[][]byte,x,yint)int{dx:[4]int{-1,1,0,0}dy:[4]int{0,0,-1,1}ifx0||xh-1||y0||yw-1{foundtrue}sum:1fori:0;i4;i{nx:xdx[i]ny:ydy[i]ifnx0||ny0||nxh||nyw||grid[nx][ny]W{continue}// 去重grid[nx][ny]Wsumdfs(grid,nx,ny)}returnsum}funcmain(){in:bufio.NewReader(os.Stdin)out:bufio.NewWriter(os.Stdout)deferout.Flush()fmt.Fscan(in,h,w)grid:make([][]byte,h)fori:0;ih;i{varsstringfmt.Fscan(in,s)grid[i][]byte(s)}ans:0fori:0;ih;i{forj:0;jw;j{ifgrid[i][j]V{foundfalsegrid[i][j]Wsum:dfs(grid,i,j)if!found{anssum}}}}fmt.Fprintln(out,ans)}