封闭村庄改建(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++
#include<bits/stdc++.h>usingnamespacestd;boolfound;inth,w;intdfs(vector<vector<char>>&grid,intx,inty){intdx[4]={-1,1,0,0};intdy[4]={0,0,-1,1};if(x==0||x==h-1||y==0||y==w-1){found=true;}intsum=1;for(inti=0;i<4;i++){intnx=x+dx[i];intny=y+dy[i];if(nx<0||ny<0||nx>=h||ny>=w||grid[nx][ny]=='W'){continue;}// 去重grid[nx][ny]='W';sum+=dfs(grid,nx,ny);}returnsum;}intmain(){cin>>h>>w;vector<vector<char>>grid(h,vector<char>(w));for(inti=0;i<h;i++){for(intj=0;j<w;j++){cin>>grid[i][j];}}intans=0;for(inti=0;i<h;i++){for(intj=0;j<w;j++){if(grid[i][j]=='V'){found=false;grid[i][j]='W';intsum=dfs(grid,i,j);if(!found){ans+=sum;}}}}cout<<ans;return0;}Java
importjava.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(x==0||x==h-1||y==0||y==w-1){found=true;}intsum=1;for(inti=0;i<4;i++){intnx=x+dx[i];intny=y+dy[i];// 越界或已经访问if(nx<0||ny<0||nx>=h||ny>=w||grid[nx][ny]=='W'){continue;}// 去重grid[nx][ny]='W';sum+=dfs(grid,nx,ny);}returnsum;}publicstaticvoidmain(String[]args)throwsException{BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));StringTokenizerst=newStringTokenizer(br.readLine());h=Integer.parseInt(st.nextToken());w=Integer.parseInt(st.nextToken());char[][]grid=newchar[h][w];for(inti=0;i<h;i++){grid[i]=br.readLine().trim().toCharArray();}intans=0;for(inti=0;i<h;i++){for(intj=0;j<w;j++){if(grid[i][j]=='V'){found=false;grid[i][j]='W';intsum=dfs(grid,i,j);if(!found){ans+=sum;}}}}System.out.println(ans);}}python
importsysinput=sys.stdin.readline found=Falseh,w=0,0defdfs(grid,x,y):globalfound dx=[-1,1,0,0]dy=[0,0,-1,1]ifx==0orx==h-1ory==0ory==w-1:found=Truesum_=1foriinrange(4):nx=x+dx[i]ny=y+dy[i]ifnx==0orny==0ornx>=horny>=worgrid[nx][ny]=='W':continue# 去重grid[nx][ny]='W'sum_+=dfs(grid,nx,ny)returnsum_ h,w=map(int,input().split())grid=[]for_inrange(h):grid.append(list(input().strip()))ans=0foriinrange(h):forjinrange(w):ifgrid[i][j]=='V':found=Falsegrid[i][j]='W'sum_=dfs(grid,i,j)ifnotfound:ans+=sum_print(ans)Javascript
constreadline=require('readline');constrl=readline.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(leti=0;i<h;i++){grid.push(lines[i+1].split(''));}letfound=false;functiondfs(x,y){constdx=[-1,1,0,0];constdy=[0,0,-1,1];if(x===0||x===h-1||y===0||y===w-1){found=true;}letsum=1;for(leti=0;i<4;i++){constnx=x+dx[i];constny=y+dy[i];if(nx<0||ny<0||nx>=h||ny>=w||grid[nx][ny]==='W'){continue;}// 去重grid[nx][ny]='W';sum+=dfs(nx,ny);}returnsum;}letans=0;for(leti=0;i<h;i++){for(letj=0;j<w;j++){if(grid[i][j]==='V'){found=false;grid[i][j]='W';constsum=dfs(i,j);if(!found){ans+=sum;}}}}console.log(ans);});Go
packagemainimport("bufio""fmt""os")varfoundboolvarh,wintfuncdfs(grid[][]byte,x,yint)int{dx:=[4]int{-1,1,0,0}dy:=[4]int{0,0,-1,1}ifx==0||x==h-1||y==0||y==w-1{found=true}sum:=1fori:=0;i<4;i++{nx:=x+dx[i]ny:=y+dy[i]ifnx==0||ny==0||nx>=h||ny>=w||grid[nx][ny]=='W'{continue}// 去重grid[nx][ny]='W'sum+=dfs(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;i<h;i++{varsstringfmt.Fscan(in,&s)grid[i]=[]byte(s)}ans:=0fori:=0;i<h;i++{forj:=0;j<w;j++{ifgrid[i][j]=='V'{found=falsegrid[i][j]='W'sum:=dfs(grid,i,j)if!found{ans+=sum}}}}fmt.Fprintln(out,ans)}
