Problem
Dada uma matriz de N (1 <= N <= 100) por M (1 <= M <= 100). A matriz contém ‘.’ – células vazias e ‘#’ – células que não podem ser visitadas. Você só pode se mover para cima, para baixo, para a esquerda e para a direita. Dadas q consultas: número da linha e número da coluna, se esta célula – ‘#’, então se torna ‘.’, caso contrário – ‘#’. Para cada uma das q consultas, determine se a célula tx;ty pode ser acessada a partir da célula Sx;Sy . Saída em cada linha “Sim”, se alcançável, e “Não” - de outra forma. É garantido que a célula Sx; Sy e célula tx; ty não são ‘#’ célula em cada solicitação.
Dados de entrada.
Na primeira linha digite os números Sx (1 <= Sx <= 100), Sy (1 < = Sy <= 100), tx (1 <= tx <= 100), ty (1 <= ty <= 100), N (1 <= N <= 100), M(1 <= M <= 100 ) e q (1 <= q <= 100). As próximas N linhas fornecem uma matriz onde ‘.’ – célula vazia e ‘#’ – uma cela que não pode ser visitada. As próximas q linhas fornecem o número da linha e o número da coluna a serem alterados.
Saída.
Imprima para cada uma das consultas q “Sim”, se da célula Sx; Sy na célula tx; ty pode ser atingido, “Não” – caso contrário.
| Entrada |
Saída |
1 1 2 3 3 3 2
.##
##.
###
1 2
2 2 |
Não
Sim |
Explicação:
Após a primeira solicitação, a matriz ficará assim:
. . #
# # .
###
Não há passagem do ponto 1;1 para 2;3, portanto, imprimimos “Não”.
Após a segunda solicitação, a matriz ficará assim:
. . #
# . .
###
Existe uma passagem do ponto 1;1 para 2;3, portanto, a saída é “Sim”. O caminho que podemos seguir está destacado.
(с) Vsevolod Shaldin