같은 좌표를 여러 번 처리하는 과정에서 큐의 순서가 정답이 보장되지 않는 것 같습니다.
늦게 값이 업데이트 될 때 누락되는 경우가 있는 것 같네요.
9
0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0
output : 144
정답 : 168

sshhss0312 1년 전
코드의 흐름으로는 우선 가로 출발상태인 끝점이 1,2인 점을 큐에 삽입 후 하나씩 꺼내어 출발 상태의 경우의 수(가로는 2개, 세로 2개, 대각선 3개)를 모두 고려하여 만족하면 큐에 삽입하는 방식으로 동작합니다. 그렇게 어떤 모양으로 도착했는지를 나눠서 dp에 값을 누적시킵니다. visited배열은 각 지점의 모양별로 한번씩만 큐에 삽입 하면 되기때문에 사용하였습니다. 제 생각엔 누락될 부분이 없는데 결과가 틀리게 나옵니다. 다음은 반례입니다. 특이하게 정답과 1씩 차이가 납니다.
8
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
출력 32 정답 33
9
0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
출력 51 정답 52
9
0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0
출력 674 정답 675