AcWing 1097. java池塘计数
原题链接
简单
作者:
mkuiwu
,
2021-02-08 10:54:30
,
所有人可见
,
阅读 279
import java.lang.*;
import java.io.*;
import java.util.*;
class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer stz = new StringTokenizer("");
static String nextLine() throws Exception {// 读取下一行字符串
return br.readLine();
}
static String next() throws Exception {// 读取下一个字符串
while (!stz.hasMoreTokens()) {
stz = new StringTokenizer(br.readLine());
}
return stz.nextToken();
}
static int nI() throws Exception {// 读取下一个int型数值
return Integer.parseInt(next());
}
static double nD() throws Exception {// 读取下一个double型数值
return Double.parseDouble(next());
}
static long nL() throws Exception {// 读取下一个double型数值
return Long.parseLong(next());
}
static void write(String str) throws Exception{
bw.write(str);
}
static String itoS(int i){
return Integer.toString(i);
}
static void wI(int i) throws Exception{
write(Integer.toString(i));
}
static void flush() throws Exception{
bw.flush();
}
public static void main(String[] args) throws Exception{
new Main().run();
}
class Point{
public int x, y;
Point(int x, int y){
this.x = x;
this.y = y;
}
}
Queue<Point> q = new LinkedList<>();
void bfs(Point p){
st[p.x][p.y] = true;
q.add(p);
while (!q.isEmpty()){
Point t = q.poll();
// 考虑八个方向
for (int i = -1; i <= 1 ; i++) {
for (int j = -1; j <= 1 ; j++) {
int a = t.x + i, b = t.y + j;
if (i == 0 && j == 0) continue;
// 合法性判断
if (a >= 1 && a <= n && b >= 1 && b <= m && g[a][b] == 'W' && !st[a][b]){
st[a][b] = true;
q.add(new Point(a, b));
}
}
}
}
}
int n, m;
final int N = 1010;
boolean[][] st = new boolean[N][N];
char[][] g = new char[N][N];
public void run() throws Exception{
n = nI(); m = nI();
for (int i = 1; i <= n; i++) {
String str = nextLine();
for (int j = 1; j <= m ; j++) {
g[i][j] = str.charAt(j-1);
}
}
int res = 0;
for (int i = 1; i <= n ; i++) {
for (int j = 1; j <= m; j++) {
char ch = g[i][j];
// 是水洼, 并且没有被遍历过
if (ch == 'W' && !st[i][j]){
res++;
bfs(new Point(i, j));
}
}
}
wI(res);
bw.write('\n');
flush();
}
}