다음은 내 솔루션이지만 문제 만 해결합니다. 동적 인 프로그래밍이나 다른 알고리즘 (무차별 대입 제외)을 사용하여 0 셀을 보드에 넣으려는 좋은 해결책을 볼 수 있기를 바랍니다.Google 코드 잼 2014 자격 인증 라운드에서 MineSweeperMaster에 대한 다른 솔루션은 무엇입니까?
set remains = r * c - m.
1) m = 0 : 모든 무료 공간입니다
다음은 내 알고리즘의 단계입니다. 인쇄하십시오. " 은 모든 셀을 "c"로 덮어 씁니다.
2) = 1 : 동일한 아이디어. 모든 셀에 "*"를 인쇄 한 다음 "c"인 셀을 덮어 씁니다.
3) r == 1 또는 c == 1 인 경우 솔루션은 첫 번째 m 셀에 "*"을 넣고 마지막 셀 에 "c"를 넣으면 다른 셀은 "."
(케이스 4의 위치와 교환) 및 5). @ TheComputerGuy의 의견에 감사드립니다.) 4) 나머지는 2, 3, 5, 7이면 "불가능"입니다. else : 012 % 2 == 2이면 만약 m % 2 == 0이면 해결 방법 : 첫 번째 m/2 열 또는 행이 "*"이고 "c "마지막 세포에서 다른 세포는". " m % 2 == 1이면 "불가능".
6) 광산을 (0,0)에서 한 줄씩, 왼쪽에서 오른쪽, 위에서 아래로 채 웁니다. 특별한 경우를 고려해야합니다. set rs = m/c; cs = m % c 6.1) rs가 < r - 2이고 cs가 < c - 1이면 잘 채워지고 마지막 셀에 "c"를 넣습니다. 다른 셀은 "."입니다. (R) -3 및 연사 == C를 -1 RS < 경우
********** ********** ********** ********** ****...... .......... ..........
6.2), 다음 라인의 시작으로 하나 내를 이동. (이 경우)
********** ********** ********** *********.(not work here) .......... .......... .......... (Final solution) ********** ********** ********** ********..(Move a * to the next row and put a space here) *......... .......... .........c
6.3) RS는 == R 경우 - 3, 연사 == C -1, 다음 두 라인
********** ********** ********** *********.(not work here) .......... .......... (Final solution) ********** ********** ********** *******...(Move a * to the next row and put a space here) *......... *........c
6.4)의 경우의 처음 두 광산 이동 - RS> = R 2, 다음 광산과 다른 셀을 첫 번째 빈 처음 두 행/2 열을 유지 떠나 채울 % 2 == 0 남아 :
c...****** ....****** ********** **********
6.5)의 경우 RS> = r - 2이고, % 2 == 1로 유지되면, N 떠나 첫 번째 (-3 남아있다) 처음 두 행/2 열 빈, 및 제 3 행의 첫 번째 세 개의 열 빈, 광산과 다른 셀을 채우기 :
c...****** ....****** ...******* **********
을 이제 모든 조건을 다룰 수 있습니다.
이 시스템을 처음 사용했습니다. 당신이 내 솔루션을 정말로 좋아한다면 약간의 크레딧을 얻길 바랍니다. 그리고 솔루션을 게시하는 것을 환영합니다. 정말 고맙습니다!
이 솔루션은 Large 테스트 케이스를 완료하는 데 단지 10 초 밖에 걸리지 않습니다. – Kenny
알고리즘에 명백한 오류가있는 경우 R = 2, C = 2 및 M = 2 인 경우도 고려하십시오. – TheComputerGuy
Thanks @ TheComputerGuy. 규칙 4)와 5)를 교환해야한다. – Kenny