Autor da análise: 
dinak
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.
Discuta o problema
Vcs trataram o caso em que a rainha anda por cima do rei branco?
A minha rainha pode atropelar o rei branco como se fosse um cavalo. E se eu tirar essa feature provavelmente nem passa.
bastaria por o caso:
c2 h2 a1
onde minha resposta dá b2
mas tá errado pq eh um movimento inválido no xadrez convencional.
Tratei. Dá "no" nesse caso.
Então a entrada não deve ter nenhum caso assim! hehe
Não tinha pensado nisso. Realmente, eu também não tratei esse caso e passou!
O que significa que a entrada tá mal feita…
É hehe deve estar mal feita, ou a rainha pode andar igual cavalo(atropelando o rei) hehe
Move rules:
The queen may move in any straight line, horizontal, vertical, or diagonal.
Isso aqui não diz que sim?
sei lá.
De fato, ele cita o jogo de xadrez como exemplo, mas não diz que o movimento da dama é exatamente como no jogo de xadrez. Assim, o caso de teste não dá WA nem para uma implementação nem para outra.
Nossa, eles devem ter colocado um monte de entradas aleatórias, e nem se preocuparam em bolar uns casos na mão pra pegar esse tipo de coisa…
mas em compensacao eles cobram caso onde o rei pode nao se mover.
(Isso pode acontecer no xadrez, vc não se mover?)
Não pode não.
Se o rei não puder se mover, e não tiver nenhuma outra peça para mover, o jogo termina empatado.