firenet.java

研究生入学考试题

import java.io.BufferedReader;
import java.io.IOException;

public class FireNet
{
    static char map[][];
    static int n, nMaxCount;

    public static void main(String args[])
    {
        java.io.BufferedReader bin = new BufferedReader(
                new java.io.InputStreamReader(System.in));
        try
        {
            n = Integer.parseInt(bin.readLine());
            map = new char[n][n];
            while (n > 0)
            {
                for (int i = 0; i < n; i++)
                {
                    String temp = bin.readLine();
                    for (int j = 0; j < n; j++)
                    {
                        map[i][j] = temp.charAt(j);
                    }
                }
                nMaxCount = 0;
                PutBlockhouses(0, 0);
                System.out.println(nMaxCount);
                n = 0;
                n = Integer.parseInt(bin.readLine());
            }
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }

    }

    static boolean CanPut(int row, int col)
    {
        int i;
        for (i = row - 1; i >= 0; i--)
        {
            if (map[i][col] == 'O')
                return false;
            if (map[i][col] == 'X')
                break;
        }
        for (i = col - 1; i >= 0; i--)
        {
            if (map[row][i] == 'O')
                return false;
            if (map[row][i] == 'X')
                break;
        }
        return true;
    }

    static void PutBlockhouses(int pos, int count)
    {
        if (pos == (n * n))
        {
            if (count > nMaxCount)
            {
                nMaxCount = count;
            }
        }
        else
        {
            int row = pos / n;
            int col = pos % n;
            if ((map[row][col] == '.') && (CanPut(row, col)))
            {
                map[row][col] = 'O';
                PutBlockhouses(pos + 1, count + 1);
                map[row][col] = '.';
            }
            PutBlockhouses(pos + 1, count);
        }
    }

}