题目描述

dfs

样例

import java.util.*;

public class Main {
    static int r, c;
    static char[][] g = new char[105][105];

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    static void dfs(int a, int b, boolean[][] st) {

        st[a][b] = true;

        for (int i = 0; i < 4; i++) {
            int x = a + dx[i];
            int y = b + dy[i];

            if (x >= 0 && x < r && y >= 0 && y < c && !st[x][y]) {
                if (g[a][b] == '0') {
                    continue;
                } else {
                    dfs(x, y, st);
                }
            }
        }
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int xun = 1;
        while (T > 0) {
            r = sc.nextInt();
            c = sc.nextInt();
            sc.nextLine();

            for (int i = 0; i < r; i++) {
                String line = sc.nextLine();
                for (int j = 0; j < c; j++) {
                    g[i][j] = line.charAt(j);
                }
            }

            int k = sc.nextInt();
            System.out.println("Case #" + xun + ":");


            while (k > 0) {
                String s = sc.next();
                if (s.equals("Q")) {
                    int res = 0;
                    boolean[][] st = new boolean[105][105];

                    for (int i = 0; i < r; i++) {
                        for (int j = 0; j < c; j++) {
                            //如果当前点为1，且这个点没被搜过
                            if (g[i][j] == '1' && !st[i][j]) {
                                dfs(i, j, st);
                                res++;
                            }
                        }
                    }
                    System.out.println(res);
                } else {
                    int i = sc.nextInt();
                    int j = sc.nextInt();
                    int data = sc.nextInt();
                    //把int类型转化为char类型
                    g[i][j] = (char) (data + '0');
                }

                k--;
            }

            T--;
            xun++;
        }

    }

}