안녕하세요, H. 지뢰찾기 문제 출제자 이태윤입니다.
작년까지는 저도 알고스팟 모의고사에 참가하며 인터넷 예선을 준비했는데, 올해에는 출제를 하게 되었네요.
이 문제는 2006년 인터넷 예선 금고 문제에서 영감(?)을 받아서 만들게 되었습니다.
가장 빠른 Yes는 대회 시작 후 79분만에 stranger님이 받았습니다.
1. 문제 설명
문제가 한글이니 생략하겠습니다.
2. 문제 풀이
막상 처음 문제를 접하면 상당히 어렵게 느껴질 수 있는데, 문제의 특수한 조건을 이용하면 쉽게 방법을 찾을 수 있습니다.
특수한 조건이란 바로 U, D, L, R이 모두 서로 다른 수라는 것입니다. 이것을 이용하면 (1,2)와 (2,1)에 지뢰 존재 여부를 알 수 있습니다.
우선 (1,1)의 위험도를 봅시다. 이 수치는 4가지가 가능합니다.
A. (1,2)와 (2,1)에 둘 다 지뢰가 없다. -> 0
B. (1,2)에는 지뢰가 없고, (2,1)에는 지뢰가 있다. -> L
C. (1,2)에는 지뢰가 있고, (2,1)에는 지뢰가 없다. -> U
D. (1,2)와 (2,1)에 둘 다 지뢰가 있다. -> L+U
L과 U가 서로 다른 수이기 때문에, 우리는 (1,1)의 위험도를 보고, (1,2)과 (2,1)에 지뢰가 있는지 알 수 있습니다.
하지만 주변 두칸의 상황을 알아도, (1,1)에는 지뢰가 존재하는지 알 수 없습니다.
그래서 (1,1)에는 지뢰가 존재하는 경우와 지뢰가 존재하지 않는 경우로 나눠서 살펴봅니다.
(1,1) (1,2) (2,1) 에서 지뢰를 모두 제거하고나면, 다시 위와 같은 방법으로 (1,2)의 수치를 보고,
(1,3)과 (2,2)에 지뢰가 있는지 알 수 있습니다. 또 (2,1)의 수치를 보고, (2,2)와 (3,1)에 지뢰가 있는지도 알 수 있습니다.
이런 식으로 왼쪽 위부터 쭉 지뢰를 찾아가면 됩니다.
3. 소스 코드
~~~ cpp

#include
#include
#include
#include
using namespace std;
#define REP(i,n) for(int i=0; i<(n); ++i)
#define N 1000
int backup[32][N+5];
int dt[32][N+5],dp[32][N+5];
int hy[4]={-1,1,0,0};
int hx[4]={0,0,-1,1};
int val[4],U,D,L,R;
int n,m;
bool remove(int y,int x)
{
int py,px;
REP(i,4) {
py=y+hy[i];
px=x+hx[i];
if (py<0 || py>=n || px<0 || px>=m) continue;
dt[py][px]-=val[i];
if (dt[py][px]<0) return false;
}
dp[y][x]=1;
return true;
}
bool isallzero()
{
REP(i,n) REP(j,m) if (dt[i][j]!=0) return false;
return true;
}
bool solve()
{
REP(i,n) REP(j,m) {
if (dt[i][j]==L)
if (!remove(i,j+1))
return false;
if (dt[i][j]==U)
if (!remove(i+1,j))
return false;
if (dt[i][j]==L+U)
if (!remove(i,j+1) || !remove(i+1,j))
return false;
}
return true;
}
int main()
{
int tn;
cin>>tn;
while (tn--) {
cin>>n>>m;
cin>>U>>D>>L>>R;
val[0]=U; val[1]=D;
val[2]=L; val[3]=R;
REP(i,n) REP(j,m) cin>>dt[i][j];
memcpy(backup,dt,sizeof(dt));
int cnt=0;
REP(qq,2) {
memcpy(dt,backup,sizeof(dt));
memset(dp,0,sizeof(dp));
if (qq)
if (!remove(0,0))
continue;
if (solve() && isallzero()) {
REP(i,n) {
REP(j,m) {
if (j) cout<<" ";
cout<<dp[i][j];
}
cout<<endl;
}
}
}
}
return 0;
}

<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/61540">원문보기</a>]</div>