세 개의 격자 그림이 주어질 때, 처음 두 그림의 XOR이 세 번째 그림과 평행 이동으로 일치하도록 두 번째 그림의 이동을 찾는다.
어려움8구현문자열 매칭완전 탐색해시맵아직 제출이 없습니다시간 제한2초메모리 제한512 MB케빈과 킴벌리는 이마에 주근깨가 있다.
둘은 각자 종이에 자기 주근깨 그림을 그렸다. 그림은 칸으로 나뉜 직사각형이고, 각 칸에는 주근깨가 있거나 없다.
둘은 나중에 결혼해서 아이를 낳으면 그 아이의 주근깨 그림이 다음 과정으로 정해진다고 농담한다. 두 그림을 평행이동해서 겹친 다음, 각 칸마다 두 사람 중 정확히 한 명만 그 자리에 주근깨가 있을 때 아이에게 그 칸의 주근깨가 생긴다.
두 사람의 그림과 아이에게 원하는 그림이 주어진다. 원하는 그림을 만드는 평행이동이 있는지 판정하고, 있다면 그 평행이동을 구하라.
한쪽을 평행이동해서 주근깨 위치가 서로 정확히 포개지면 두 그림은 같은 그림이다. 주근깨 둘레의 빈 행과 빈 열은 따지지 않는다.
첫 줄에 케빈의 그림의 높이와 너비를 나타내는 정수 h1, w1 (1≤h1,w1≤1000)이 주어진다. 다음 h1개 줄에는 각각 *와 .로 이루어진 w1개의 문자가 주어진다. *는 주근깨가 있는 칸, .는 주근깨가 없는 칸이다.
이어서 킴벌리의 그림이 같은 형식으로 주어진다. 높이 h2와 너비 w2의 범위는 위와 같다.
마지막으로 아이에게 원하는 그림이 같은 형식으로 주어진다. 높이 h3과 너비 w3의 범위도 위와 같다.
세 그림에는 각각 주근깨가 적어도 하나 있다.
원하는 그림을 만들 수 있으면 첫 줄에 YES를, 만들 수 없으면 NO를 출력한다.
만들 수 있으면 둘째 줄에 정수 x와 y를 출력한다. 두 그림의 왼쪽 위 모서리를 맞춰 겹친 뒤 킴벌리의 그림을 오른쪽으로 x칸 (x가 음수면 왼쪽으로), 아래로 y칸 (y가 음수면 위로) 옮기고 위 과정을 적용하면, 그 결과를 평행이동해서 원하는 그림과 정확히 포갤 수 있어야 한다.
조건을 만족하는 (x,y)가 여럿이면 x가 가장 작은 것을 출력하고, 그런 것이 여럿이면 그중 y가 가장 작은 것을 출력한다.