[editorial] H. 지뢰찾기

  • Taeyoon_Lee
    Taeyoon_Lee

    안녕하세요, 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. 소스 코드

    #include <algorithm>
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    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;
    }
    
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    14년 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.