算法1

dfs

Flood fill中dfs解法，从起点出发，向四周进行深度优先遍历搜索

时间复杂度 $O(nm)$

最多是$nm$个点

参考文献

算法提高课

Java 代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 25;
    static int m;
    static int n;
    static char[][] g = new char[N][N];
    static boolean[][] st = new boolean[N][N];//记录该点是否遍历过
    static int[] dx = new int[] {-1,0,1,0};
    static int[] dy = new int[] {0,1,0,-1};
    static int dfs(int x,int y)
    {
        int cnt = 1;
        st[x][y] = true;
        for(int i = 0;i < 4;i++)
        {
            int a = x + dx[i];
            int b = y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(g[a][b] != '.') continue;
            if(st[a][b]) continue;
            cnt += dfs(a,b);
        }
        return cnt;
    }
    public static void main(String[] args)  {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext())
        {
            m = scan.nextInt();
            n = scan.nextInt();
            if(m == 0 && n == 0) break;
            int x = 0;
            int y = 0;
            for(int i = 0;i < n;i ++)
            {
                Arrays.fill(st[i], false);
                char[] charArray = scan.next().toCharArray();
                for(int j = 0;j < m;j ++)
                {
                    g[i][j] = charArray[j];
                    if(g[i][j] == '@')
                    {
                        x = i;
                        y = j;
                    }
                }
            }
            System.out.println(dfs(x,y));
        }

    }
}

算法2

bfs

Flood fill中bfs解法，从起点出发，向四周进行广度优先遍历搜索

时间复杂度 $O(nm)$

最多是$nm$个点

参考文献

算法提高课

Java 代码

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int N = 25;
    static int m;
    static int n;
    static char[][] g = new char[N][N];
    static boolean[][] st = new boolean[N][N];//记录该点是否遍历过
    static int[] dx = new int[] {-1,0,1,0};
    static int[] dy = new int[] {0,1,0,-1};
    static int bfs(int x,int y)
    {
        Queue<PIIs> q = new LinkedList<PIIs>(); 
        q.add(new PIIs(x,y));
        st[x][y] = true;
        int cnt = 1;
        while(!q.isEmpty())
        {
            PIIs t = q.poll();
            for(int i = 0;i < 4;i++)
            {
                int a = t.x + dx[i];
                int b = t.y + dy[i];
                if(a < 0 || a >= n || b < 0 || b >= m) continue;
                if(g[a][b] != '.') continue;
                if(st[a][b]) continue;
                cnt ++;
                st[a][b] = true;
                q.add(new PIIs(a,b));
            }
        }
        return cnt;
    }
    public static void main(String[] args)  {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext())
        {
            m = scan.nextInt();
            n = scan.nextInt();
            if(m == 0 && n == 0) break;
            int x = 0;
            int y = 0;
            for(int i = 0;i < n;i ++)
            {
                Arrays.fill(st[i], false);
                char[] charArray = scan.next().toCharArray();
                for(int j = 0;j < m;j ++)
                {
                    g[i][j] = charArray[j];
                    if(g[i][j] == '@')
                    {
                        x = i;
                        y = j;
                    }
                }
            }
            System.out.println(bfs(x,y));
        }
    }
}
class PIIs
{
    public int x;
    public int y;
    public PIIs(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
}