(UVA) 167 - The Sultan's Successors - 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);
    }

    static int leitor(BufferedReader br) throws NumberFormatException, IOException {
        int n;
        int resp = 0;
        
        while (true) {
            n = br.read();
            if (n >= '0' && n <= '9') break;
        }
        while (true) {
            resp = resp*10 + n-'0';
            n = br.read();
            if (n < '0' || n > '9') break;
        }
        
        return resp;
    
    }
   
    int funcao (int[][] matriz, int coluna, int[] vetorConfereLinha, int[] vetorConfereColuna, int[] vetorDiagonal1, int[] vetorDiagonal2, int valor) {
        if (coluna == 8) { // viu tudo - conseguiu colocar rainha em todas as colunas
            return valor;
        }
       
        int resposta = 0;
       
        for (int i = 0; i < 8; i++) {
            int indice1 = i+coluna;
            int indice2 = i+8-coluna-1;
            if (vetorConfereLinha[i] > 0 || vetorConfereColuna[coluna] > 0 || vetorDiagonal1[indice1] > 0 || vetorDiagonal2[indice2] > 0) {
                continue;
            }
            valor += matriz[i][coluna];
           
            vetorConfereLinha[i] += 1;
            vetorConfereColuna[coluna] += 1;
            vetorDiagonal1[indice1] += 1;
            vetorDiagonal2[indice2] += 1;

            resposta = Math.max(resposta, funcao(matriz, coluna+1, vetorConfereLinha, vetorConfereColuna, vetorDiagonal1, vetorDiagonal2, valor));
                      
            valor -= matriz[i][coluna];   

            vetorConfereLinha[i] -= 1;
            vetorConfereColuna[coluna] -= 1;
            vetorDiagonal1[indice1] -= 1;
            vetorDiagonal2[indice2] -= 1;
        }

        return resposta;
    }
   
    void processa() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int qteCasos = leitor(br);
       
        while (qteCasos > 0) {
            qteCasos--;
            int[][] matriz = new int[8][8];

            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {                   
                    matriz[i][j] = leitor(br);
                }
            }
           
            int[] vetorLinha = new int[8];
            int[] vetorColuna = new int[8];
            int[] vetorDiagonal1 = new int[16];
            int[] vetorDiagonal2 = new int[16];
            int resposta = funcao(matriz, 0, vetorLinha, vetorColuna, vetorDiagonal1, vetorDiagonal2, 0);
                
            int qteDigitos = 0;
            int respostaBkp = resposta;
            while (resposta > 0) {
                qteDigitos += 1;
                resposta /= 10;
            }       
           
            for (int i = 0; i < (5-qteDigitos); i++) {
                bw.write(" ");
            }       
            bw.write(respostaBkp + "\n");
        }
       
        bw.flush();
        bw.close();           
        return;
    }
}

Comments

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução