算法1

(BFS+FloodFill) $O(n^2)$

时间复杂度

参考文献

JAva 代码

package Acwing1233;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;
class Block
{
    int x,y;
    public Block(int x,int y)
    {
        this.x=x;
        this.y=y;
    }
}
public class Main {
    static int n;
    static char map[][]=new char[1010][1010];
    static int dir[][]= {{0,1},{0,-1},{1,0},{-1,0}};
    static int res=0;
    private static boolean BFS(int x,int y)
    {
        Queue<Block> q=new LinkedBlockingQueue<Block>();
        q.add(new Block(x, y));
        int total=0;
        int bound=0;
        while(!q.isEmpty())
        {
            Block tmp=q.poll();
            total++;
            boolean flag=false;
            for(int i=0;i<4;i++)
            {
                int newx=tmp.x+dir[i][0];
                int newy=tmp.y+dir[i][1];
                if(newx<1||newx>n||newy<1||newy>n)  continue;
                if(map[newx][newy]=='.') flag=true;
                if(map[newx][newy]=='#')    q.add(new Block(newx,newy));
            }
            if(flag) bound++;
            map[tmp.x][tmp.y]='p';
        }
        return total==bound;
    }
    public static void main(String args[]) throws IOException
    {
        BufferedReader b=new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(b.readLine());
        for(int i=1;i<=n;i++)
        {
            String tmp=b.readLine();
            for(int j=1;j<=n;j++)
            {
                map[i][j]=tmp.charAt(j-1);
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(map[i][j]=='#')
                {
                    res++;
                    if(!BFS(i,j))   res--;
                }
            }
        }
        System.out.println(res);
    }
}