bfs
bfs算法模板
抽象题意
给你一个二维矩阵的图,让你在这个图中求有多少个连通块。
算法1
blablabla
java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static int N=1010,M=1010;
public static int n,m;
public static char[][] g=new char[N][M];
public static Queue<Pair> q=new LinkedList<>();
public static boolean[][] st=new boolean[N][M];
public static int res;
public static int[] dx={-1,-1,0,1,1,1,0,-1};
public static int[] dy={0,1,1,1,0,-1,-1,-1};
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
n=Integer.parseInt(s[0]);
m=Integer.parseInt(s[1]);
for(int i=0;i<n;i++){
String s1 = br.readLine();
for(int j=0;j<m;j++){
g[i][j]=s1.charAt(j);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(g[i][j]=='W' && !st[i][j]){
bfs(i,j);//每一次把一个点作为起点,投入bfs中遍历,此时bfs就会把所有能遍历到的点都遍历了。
res++;
}
}
}
System.out.println(res);
}
public static void bfs(int sx,int sy){
Pair p=new Pair(sx,sy);
q.add(p);
st[sx][sy]=true;
while(!q.isEmpty()){
Pair t=q.poll();//出队
for(int i=0;i<8;i++){//遍历从这个点能到的所有点
int x=t.x+dx[i];
int y=t.y+dy[i];
if(x<0||x>=n||y<0||y>=m){//特判
continue;
}
if(st[x][y]||g[x][y]=='.'){//特判
continue;
}
q.add(new Pair(x,y));//入队
st[x][y]=true;//标记
}
}
}
}
class Pair{
int x;
int y;
public Pair(int x,int y){
this.x=x;
this.y=y;
}
}