PKU 1647 - One-move checkmate

Autor da análise: dinakdinak

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1647

Resumo

Dadas as posições do rei branco, dama branca e do rei preto, determinar se no próximo movimento com a dama branca é possível dar cheque-mate. Em caso negativo exibir "no", em caso positivo, exibir a casa onde a dama branca deverá pousar para tal. Na entrada, o rei preto nunca se encontra em cheque e, naturalmente, estará uma casa distante do rei branco.

Solução

Todas tentativas total!!! Eu modelei dentro de uma matriz de char 8 por 8 e só fui atualizando.
Dada a entrada: f7 b2 h7, temos (o B é do rei preto):

+ + + + + + + +
+ Q + + + + + +
+ + + + + + + +
+ + + + + + + +
+ + + + + + + +
+ + + + + + K +
+ + + + + + + +
+ + + + + + B +

Eu preenchi conforme os seguintes passos:

Preencha as possíveis casas da dama:

q q q + + + + +
q Q q q q q q q
q q q + + + + +
+ q + q + + + +
+ q + + q + + +
+ q + + + q K +
+ q + + + + q +
+ q + + + + B q

Para cada q no tabuleiro, faça um cópia do tabulerio e processe assim:

Preencha as possíveis casa do rei preto:

q q q + + + + +
q Q q q q q q q
q q q + + + + +
+ q + q + + + +
+ q + + q + + +
+ q + + + q K +
+ q + + + b b b
+ q + + + b B b

Preencha a partir do q escolhido (aqui B1) as casas onde a dama atinge (usei m):

m m q + + + + +
M m m m m m m m
m m q + + + + +
m q m q + + + +
m q + m q + + +
m q + + m q K +
m q + + + m b b
m q + + + b m b

Depois eu verifico se sobrou algum b no tabuleiro, se não sobrou então é cheque-mate. No caso acima, é possível ver que tem 4 casas com b, isso quer dizer que se eu posicionar a dama na posição M, o rei preto poderia escapar para uma dessas casas. No caso de não achar nenhum b, mas ter ainda um B, significa que o rei preto não tem para onde se mover e a dama não conseguiu ameaçar o rei, logo é um empate, e retorno "no".

Mas tem 2 casos ainda a serem tratados, se o rei preto consegue capturar a dama, e ainda, se isso for possível, verificar se o rei branco não impede essa captura.

No caso abaixo, o rei preto consegue captura a dama:

m q q + + + + +
q m q q q q q q
q q m + + + + +
+ q + m + + + +
+ q + + m + + +
+ q + + + m K m
m m m m m m M m
+ q + + + m m m

Entretanto, antes de preencher conforme está acima, eu verifico se na posição onde vou colocar a dama (marcada com M) tem um b, e de fato tinha, então eu não coloco o M lá, mas sim o b. Logo, o preenchimento acima não existiria, o que de fato ficaria está abaixo:

m q q + + + + +
q m q q q q q q
q q m + + + + +
+ q + m + + + +
+ q + + m + + +
+ q + + + m K m
m m m m m m b m
+ q + + + m m m

Com esse b aí, significaria que o rei preto tinha um lugar para escapar (por hora, desconsidere o rei branco), que era capturando a dama, assim, a verificação de cheque-mate falharia. Mas, de fato, o rei branco existe, e esse é outro caso a tratar.

Antes da verificação, preencha as possíveis casas do rei branco:

m q q + + + + +
q m q q q q q q
q q m + + + + +
+ q + m + + + +
+ q + + m k k k
+ q + + + k K k
m m m m m k k k
+ q + + + m m m

Agora é possível fazer a verificação e o cheque-mate seria confirmado, pois não existe nenhum b no tabuleiro.

O algoritmo resulta "no" quando para cada q testado, existiu pelo menos um b em algum lugar, e portanto não havia onde posicionar a dama para um mate.

Embora o pessoal disse ser desnecessário verificar se o rei branco impedia o deslocamento da dama, eu implementei isso, por exemplo, para f7 b3 h7, eu tinha:

+ q q q + + + +
q q Q q q q q q
+ q q q + + + +
q + q + q + + +
+ + q + + q + +
+ + q + + + K +
+ + q + + + + +
+ + q + + + B +

Essa regra valia para quando eu preenchia com m.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License