프로그래밍 퍼즐 : 보드를 페인트하는 방법?

Question

페인트해야 할 N x M 보드가 있습니다. 한 번에 전체 행이나 전체 열을 칠할 수 있습니다. 모든 보드 셀의 색상의 N x M 행렬이 주어지면 보드를 페인트하기위한 최소한의 페인트 작업 횟수를 찾습니다.

B, B, B
B, R, R
B :

예를 들어, (- 레드, B - - G, 청색, 녹색 R)은 다음과 같이 우리는 3 × 3 판의 색칠 페인팅 작업 G, G는

최소 수는 4 : 레드,745 블루

페인트 행 1

• 페인트 행 0 블루

녹색

페인트 열

페인트 행이 어떻게 그것을 해결할 것인가?

Answer 1

처음에는 의 정보 검색 철저한 검색을 시도해 볼 수 있습니다.

귀하의 주 그래프가 G=(V,E) 인 경우, V = {all possible boards} 및 E = {(u,v) | you can move from board u to v within a single operation}입니다. 당신은 즉시 그것을 생성 할 수 있습니다, 주어진 보드의 모든 후임자를 돌려 successors(board) 기능을 사용하여 - 당신이 사전에 그래프를 생성 할 필요가 없습니다

• 참고.

는 또한 h:V->R해야합니다 - 보드 ¹을 평가하는 admissible heuristic function을.

이제 A* 또는 bi-directional BFS 검색 [또는 둘 모두의 조합]을 실행할 수 있습니다. 소스가 화이트 보드이고 타겟이 요청한 보드입니다. 허용 가능한 휴리스틱 함수를 사용하기 때문에 - A *는 complete (항상 존재하는 경우 솔루션을 찾습니다)과 optimal (가장 짧은 솔루션을 찾습니다) 둘 다 최상의 솔루션을 찾습니다. [양방향 BFS의 경우도 마찬가지입니다.]

단점 : 알고리즘이 통보

• 있지만, 그것은 지수 행동을해야합니다. 그러나 인터뷰 질문 인 경우 비효율적 인 솔루션이 더 나은 솔루션이라고 생각합니다.
• 해결책이 없다면 알고리즘은 무한 루프에 붙어있을 수도 있고, 매우 긴 루프가 적어도 모든 가능성을 보여줄 때까지 멈출 수 있습니다. 허용 추론

(1) 예를 들어이 재미있는 문제처럼 보인다 h(board) = #(miscolored_squares)/max{m,n}

Answer 2

입니다. 몇 가지 의사 코드로 그 장면을 촬영하겠습니다.

Function MinPaints(Matrix) Returns Integer 
    If the matrix is empty return 0 
    Find all rows and columns which have a single color 
    If there are none, return infinity, since there is no solution 
    Set the current minimum to infinity 
    For each row or column with single color: 
     Remove the row/column from the matrix 
     Call MinPaints with the new matrix 
     If the result is less than the current minimum, set the current minimum to the result 
    End loop 
    Return the current minimum + 1 
End Function 

나는 당신의 문제를 해결할 것이라고 생각하지만, 어떤 최적화 또는 아무것도 시도하지 않았다. 이것은 충분히 빠르지 않을 수도 있지만, 나도 몰라. 나는이 문제가 지수 이하의 시간에 해결 될 수 있을지 의심 스럽다.

BBB 
BRR 
BGG 
| 
+---BRR 
| BGG 
| | 
| +---RR 
| | GG 
| | | 
| | +---GG 
| | | | 
| | | +---[] 
| | | | | 
| | | | Solvable in 0 
| | | | 
| | | Solvable in 1 
| | | 
| | +---RR 
| | | | 
| | | +---[] 
| | | | | 
| | | | Solvable in 0 
| | | | 
| | | Solvable in 1 
| | | 
| | Solvable in 2 
| | 
| Solvable in 3 
|      BB 
+---Another branch with RR ... 
|      GG 
Solvable in 4