Codeforces Round #802 (Div. 2) E. Serega the Pirate

Problem - E - Codeforces

어떤 한 셀에서 인접한 4개 이하의 셀들에 대해 자기 자신보다 값이 작은 셀이 존재한다면 그 셀까지 경로는 존재한다.

만약 어떤 한 셀의 인접한 4개 이하의 셀들이 전부 자기 자신보다 값이 클 경우 그 셀을 에러 셀이라고 하자.

에러 셀이 0개인 경우는 답이 0이다.

에러 셀이 1개 ~ 8개 사이인 경우는 답이 1 또는 2이고 에러 셀이 8개보다 클 경우 답이 2이다.

에러 셀이 1개 ~ 8개 사이인 경우를 체크해 줘야 하는데 두 개의 셀이 스왑 했을 때 상태변화가 일어나는 셀은 바뀐 셀의 인접한 8개의 셀들이다.

따라서 만약 1번 스왑만에 모든 셀들이 에러가 아니게 만들려면 무조건 스왑 하는 두 셀 중 한 셀은 어떤 에러 셀의 인접해야 한다.

따라서 아무거나 에러 셀을 하나 잡고 그 셀의 인접한 4개의 셀과 그 에러 셀 1개 총 5개의 셀을 전부 모든 셀과 스왑 한다.

그리고 상태변화가 일어난 셀들과 에러 셀들을 다시 체크해서 전체에 에러 셀이 없는지 확인한다.

만약 전체에 에러 셀이 없다면 답은 1이고 그러한 스왑이 존재하지 않는다면 답은 2이다.

에러 셀의 인접한 4개와 그 에러 셀 1개 총 5개의 셀과 nm 개의 셀을 전부 스왑 하니까 경우의 수는 총 5 * 40만 = 200만 개.

각 각 스왑하고 나서 테스트해야 할 셀들은 스왑 셀 2개의 인접한 셀들 8개 + 에러 셀 8개의 인접한 셀들 24개 = 총 32개 이므로 200만 * 32 = 6400만 번 연산으로 답을 도출할 수 있다.