问题
다락방에 있는 오래된 장난감 상자에서 이상한 퍼즐을 발견했습니다. 이 퍼즐은 h×w 개의 정사각형 칸으로 이루어진 직사각형 격자판 형태입니다. 그림 1과 같이 격자의 일부 칸에는 색칠된 타일이 놓여 있습니다.
그림 1: 색칠된 타일은 예제 입력 1의 시작 배치에 해당합니다.
이 퍼즐의 정확한 목표가 무엇인지는 아직 확실하지 않지만, 타일을 재배치하는 가능한 방법들을 살펴보기 시작했습니다. 타일의 배치는 격자를 왼쪽, 오른쪽, 앞쪽, 뒤쪽의 네 가지 기본 방향 중 하나로 기울여서 조작할 수 있습니다. 격자를 기울이면 모든 타일이 경계선이나 다른 타일에 막힐 때까지 해당 방향으로 미끄러집니다. 시작 배치와 종료 배치가 주어졌을 때, 시작 배치를 종료 배치로 변환하는 일련의 기울이기 동작이 존재하는지 확인하십시오. 그림 2는 예제 입력 1에 표시된 퍼즐의 기울이기를 보여줍니다.
그림 2: 예제 입력 1에 대한 해답.
输入
입력의 첫 번째 줄에는 격자의 높이와 너비를 나타내는 두 정수 .)입니다. 타일이 있는 경우, 해당 타일의 색상이 알파벳 소문자(a-z)로 주어집니다. 서로 다른 문자는 서로 다른 색을 나타내며, 같은 색의 타일은 서로 구별할 수 없습니다.
시작 배치 뒤에는 빈 줄이 하나 있고, 이어서 시작 배치와 같은 형식의 h$h$개의 줄로 이루어진 종료 배치의 설명이 나옵니다.
示例 #1
4 4
.r..
rgyb
.b..
.yr.
yrbr
..yr
...g
...b
yes
示例 #2
1 7
....x..
..x....
no
示例 #3
4 3
yr.
..b
ry.
b..
...
..b
.ry
byb
no
需要登录才能编写代码。