(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;
}
}
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
Post a Comment