(UVA) 639 - Don't Get Rooked - Solução

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main processando = new Main();
        processando.processa();
       
        System.exit(0);
    }

    int funcao (int[][] matriz, int tamanho, int linha, int coluna, int qteTorres) {
        if (coluna == tamanho) {
            return qteTorres;
        }
       
        int resposta = qteTorres;

        for (int i = linha; i < tamanho; i++) {
            int valorCampo = matriz[i][coluna];
           
            if (matriz[i][coluna] > 0 && i < tamanho-1) { // dominado por uma torre e não é X, tenta a próxima linha
                continue;
            }

            // se não tá dominado por uma torre e é X
            if (valorCampo == 0) {
                qteTorres++;
           
                for (int j = coluna; j < tamanho; j++) {
                    if (matriz[i][j] == -1) { // é X
                        break;
                    }
                    else {
                        matriz[i][j] += 1;
                    }
                }
                for (int j = i+1; j < tamanho; j++) {
                    if (matriz[j][coluna] == -1) { // é X
                        break;
                    }
                    else {
                        matriz[j][coluna] += 1;
                    }
                }
            }
           
            int lin = 0;
            int col = 0;           
            if (i == tamanho-1) { // tá no limite das linhas
                lin = 0;
                col = coluna+1;
            }
            else {
                lin = i+1;
                col = coluna;
            }
           
            resposta = Math.max(resposta, funcao(matriz, tamanho, lin, col, qteTorres));
           
            if (valorCampo == 0) {
                qteTorres--;
           
                for (int j = coluna; j < tamanho; j++) {
                    if (matriz[i][j] == -1) { // é X
                        break;
                    }
                    else {
                        matriz[i][j] -= 1;
                    }
                }
                for (int j = i+1; j < tamanho; j++) {
                    if (matriz[j][coluna] == -1) { // é X
                        break;
                    }
                    else {
                        matriz[j][coluna] -= 1;
                    }
                }
            }           
        }
               
        return resposta;
    }
   
    void processa() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String line = "";
        line = br.readLine();
        StringTokenizer tokenizer = new StringTokenizer(line);
        int tamanho = Integer.valueOf(tokenizer.nextToken());
       
        while (tamanho != 0) {
            int[][] matriz = new int[tamanho][tamanho];

            for (int i = 0; i < tamanho; i++) {
                line = br.readLine();
                for (int j = 0; j < tamanho; j++) {
                    char lido = line.charAt(j);
                    if (lido == 'X') {
                        matriz[i][j] = -1;
                    }
                    else if (lido == '.') {
                        matriz[i][j] = 0;
                    }
                }
            }
           
            int resposta = funcao(matriz, tamanho, 0, 0, 0);
                   
            bw.write(resposta + "\n");
           
            line = br.readLine();
            tokenizer = new StringTokenizer(line);
            tamanho = Integer.valueOf(tokenizer.nextToken());
        }
       
        bw.flush();
        bw.close();           
        return;
    }
}