데이터센터 듀플렉스 timer 20s memory 1024MB

Apricot Rules LLC와 Banana Rocks Inc.라는 두 회사가 같은 데이터센터를 공유하고 있다. 데이터센터는 R행 C열의 행렬이며, 각 칸에는 서버 타워가 하나씩 있다. 각 타워에는 두 회사 중 정확히 한 회사의 지적 재산이 들어 있다.

처음에 두 회사는 서로 다른 회사에 배정된 인접한 두 칸 사이의 변(모서리)에 벽을 세웠다. 이렇게 하면 같은 회사에 속한 칸들이 상하좌우로 인접해 있을 때 서로 연결된 상태로 남게 된다. 또한 어떤 칸 x가 y와 (직접 또는 간접적으로) 연결된 어떤 칸과 연결되어 있다면, x와 y는 연결되어 있다고 정의한다. 이 정의에 따르면 같은 회사에 배정된 두 칸이 서로 연결되어 있지 않을 수도 있는데, 이는 받아들일 수 없었다.

두 회사는 두 칸이 대각선으로 인접할 때에도 직접 연결될 수 있도록, 칸의 꼭짓점을 통과하는 좁은 통로(hallway)를 만들기로 합의했다. (i, j)를 i행 j열의 칸이라고 하자. 어떤 꼭짓점 하나를 통해서는 좁은 통로를 최대 하나만 만들 수 있다. 즉, (i, j)와 (i + 1, j + 1)을 연결하거나, (i + 1, j)와 (i, j + 1)을 연결하거나, 혹은 둘 다 연결하지 않거나 중 하나만 가능하며, 두 쌍을 동시에 연결할 수는 없다. 물론 같은 회사에 배정된 칸들 사이에만 통로를 만들 수 있다.

각 칸이 어느 회사에 배정되었는지에 따라 A 또는 B로 라벨링된 행렬이 주어질 때, 대각선 인접 연결을 적절히 추가하여 모든 A 칸이 서로 연결되고, 모든 B 칸도 서로 연결되게 만드는 방법을 찾아라.