POJ 1164 The Castle 深搜入门（城堡问题）

题意：计算城堡一共有多少房间，最大的房间有多大（多少方块数构成最大的房间）？
城堡被分割成 R × C（R <= 50，C <= 50），每个方块可以有 0-4 面墙（1-西面有墙，2-北面有墙，4-东面有墙，8-南面有墙），例如：13-表示东南西三面有墙。

深度优先遍历图 VS 广度优先遍历图

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    private static final int MAX_SIZE = 60;

    private static int rooms[][] = new int[MAX_SIZE][MAX_SIZE];       // 房间编号
    private static boolean pass[][] = new boolean[MAX_SIZE][MAX_SIZE];// 记录房间是否路过
    private static int roomArea;    // 房间所包括的方块数

    private static void DFS(int indexI, int indexJ) {
        // 直到所有的顶点都被访问
        if (pass[indexI][indexJ]) {
            return;
        }
        pass[indexI][indexJ] = true;// 标记已访问房间
        ++roomArea;                 // 房间所包括的方块数+1
        // 向西走
        if ((rooms[indexI][indexJ] & 1) == 0) {
            DFS(indexI, indexJ - 1);
        }
        // 向北走
        if ((rooms[indexI][indexJ] & 2) == 0) {
            DFS(indexI - 1, indexJ);
        }
        // 向东走
        if ((rooms[indexI][indexJ] & 4) == 0) {
            DFS(indexI, indexJ + 1);
        }
        // 向南走
        if ((rooms[indexI][indexJ] & 8) == 0) {
            DFS(indexI + 1, indexJ);
        }

    }

    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        int maxRoomArea = 0;        // 房间包含的方块数的最多数量
        int roomNum = 0;            // 房间的数量
        int inputR;                 // 行
        int inputC;                 // 列
        while (in.hasNext()) {
            inputR = in.nextInt();
            inputC = in.nextInt();
            for (int indexI = 0; indexI < inputR; indexI++) {
                for (int indexJ = 0; indexJ < inputC; indexJ++) {
                    rooms[indexI][indexJ] = in.nextInt();  // 第二个 case 时，不需要重新初始化。因为有围墙包着。
                }
                Arrays.fill(pass[indexI],false);
            }
            for (int indexI = 0; indexI < inputR; indexI++) {
                for (int indexJ = 0; indexJ < inputC; indexJ++) {
                    // 如果图中顶点未被访问过
                    if (!pass[indexI][indexJ]) {
                        ++roomNum;          // 房间数 + 1
                        roomArea = 0;       // 初识房间所包含的方块数为 0
                        DFS(indexI, indexJ);// 一个顶点起，进行深度优先遍历
                        maxRoomArea = roomArea > maxRoomArea ? roomArea : maxRoomArea;
                    }
                }
            }
            out.println(roomNum);
            out.println(maxRoomArea);
        }
        out.flush();
    }
}