| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 40 | 10 | 10 | 50.000% |
격자 아티스트 브루는 $N\times M$ 크기의 격자를 가지고 있다. 격자의 위에서부터 $r$번째 행, 왼쪽에서부터 $c$번째 열의 칸을 $(r,c)$와 같이 표기한다. 브루는 격자를 여러 조각으로 자르려고 한다.
격자를 자를 때는 $NM$개의 모든 격자칸에 대해 각각 자를 방향을 정해야 한다. 각 칸을 자르는 방향은 두 대각선 방향 중 하나여야 한다.
아래 그림은 4ドル\times 4$ 크기의 격자판을 자르는 한 가지 예시를 나타낸다.
위의 그림과 같이 자를 경우, 이 격자판은 총 9ドル$개의 조각으로 나뉘어진다.
다음 조건을 만족하는 조각을 아름다운 조각이라고 하자.
브루는 격자를 더 아름답게 자르는 방법에 대해 연구하던 중, 격자에 있는 변에 관심을 가지기 시작했다. 변의 정의는 아래와 같다.
정의에 따라, $N\times M$ 크기의 격자에는 총 $(N-1) M$개의 가로변과 $N(M-1)$개의 세로변이 존재함을 알 수 있다.
브루는 $NM$개의 칸 중 일부 칸은 자를 방향을 이미 정했지만, 나머지 칸들은 아직 자를 방향을 정하지 않았다. 또한, 브루는 특정한 $K$개의 변이 아름다운 조각에 속하기를 원한다. (해당 변들이 같은 조각에 속할 필요는 없다.)
위의 조건을 만족하도록 격자를 자르는 방법이 존재하는지 알아내고, 만약 존재한다면 그러한 방법을 하나 찾아보자.
첫 줄에는 세 정수 $N,ドル $M,ドル $K$가 공백으로 구분되어 주어진다. (2ドル\le N\le 50$; 2ドル\le M\le 50$; 0ドル\le K\le(N-1) M+N(M-1)$)
이후 $N$개의 줄에 걸쳐, 그중 $r$번째 줄에는 브루가 각 칸을 자를 방향을 나타내는 $M$개의 문자 $C_{r1},ドル $C_{r2},ドル $\cdots,ドル $C_{rc}$가 주어진다. $C_{rc}$는 '/', '\', '.' 중 하나이다.
'/' 또는 '\'인 경우 격자칸 $(r,c)$를 자를 방향을 나타낸다.'.'인 경우 격자칸 $(r,c)$를 자를 방향을 아직 정하지 않았다는 것을 의미한다.이후 $K$개의 줄에 걸쳐, 그중 $i$번째 줄에는 아름다운 조각에 포함되어야 하는 $i$번째 변을 나타내는 세 정수 $d_i,ドル $a_i,ドル $b_i$가 주어진다. $K$개의 변은 서로 다르다. (0ドル\le d_i\le 1$; 1ドル\le a_i\le N-(1-d_i)$; 1ドル\le b_i\le M-d_i$)
입력으로 주어진 $K$개의 변이 모두 아름다운 조각에 속하도록 격자를 자르는 방법이 존재한다면, 첫 줄에 "YES"를 출력한다.
다음 $N$개의 줄에는 격자를 자르는 방법을 출력한다. 각 줄에는 $M$개의 문자를 출력하며, 각 문자는 '/' 또는 '\' 중 하나여야 한다.
만약 그러한 방법이 존재하지 않는다면 첫 줄에 "NO"를 출력한다.
4 4 2 ..// .\./ .\.. \./\ 0 3 3 1 3 1
YES \\// /\\/ \\\/ \\/\
2 3 2 .\. ... 1 2 1 1 2 2
NO