2014 Qualification C - Minesweeper Master

domen111

https://code.google.com/codejam/contest/2974486/dashboard#s=p2


題意:
給你一個踩地雷遊戲的長寬(RxC)，以及裡面有幾個地雷(M)，叫你排出踩地雷遊戲的地雷位置，請問你有沒有辦法點一次就讓玩家獲勝?
踩地雷遊戲介紹:
遊戲開始時，玩家可看到一堆整齊排列的空白方塊，方塊數為RxC。如果玩家點開方塊後沒有地雷，會有一個數字顯現其上，這個數字代表著鄰近方塊有多少顆地雷（數字至多為8），玩家須運用邏輯來推斷哪些方塊含或不含地雷。 (修改自維基百科)
當你踩到數字是0時，四周的方塊會自動點開，如果旁邊自動點開的的方塊也是0，會再自動把相鄰的方塊點開，直到旁邊都不是0為止。

輸入說明:第一行代表有幾筆測資。
每筆測資占一行，有三個數字R,C,M。
輸出說明:
先輸出:「Case #x:」，x代表第幾筆測資(從1開始編號)
如果不可能玩家一次獲勝，輸出「Impossible」
如果可能，輸出一種可能的盤面。「c」代表玩家按下的位置，「.」代表沒地雷，「*」代表地雷。

範例輸入:

5 5 5 23 3 1 1 2 2 1 4 7 3 10 10 82

範例輸出:

Case #1: Impossible Case #2: c . * Case #3: Impossible Case #4: ......* .c....* ....... ..*.... Case #5: ********** ********** ********** ****....** ***.....** ***.c...** ***....*** ********** ********** **********

範例測資說明:
Case 1:
5*5的方格，有23個地雷，不可能一次完成。
例如擺成這種盤面:

.**** .**** ***** *****

左上角兩格分別是2、4

題目解法:我原本的想法是辨識一些樣型，用一堆if去判斷(HSCHE這你比較擅長)，而且我看了前幾名的程式碼也類似這樣。
這題感覺很有意思，如果認真想會想到很多的狀況，得判斷很多東西，當看到好的解法時才會發現這個解法的厲害，建議自己先想想看再看解法。
比較好的算法:
參考: GCJ – Minesweeper Master | Reflections of Dusk
假設要把沒地雷的地方留在左上腳，就先把右邊和左邊慢慢填滿，如圖:3*5的盤面，10個地雷 (灰色代表地雷)
一開始的樣子:

填滿右邊或下面，右邊行數較少，填滿右邊:


繼續填右邊:


長寬都剩下三，填右邊或下面皆可:

剩1顆地雷無法填滿一整行(右邊那行需要2顆地雷):

這時候你會發現遇到問題了，玩家無法一次獲勝，於是發現這題是Impossible。
但並不是這樣就一定是Impossible，換個範例:

你會發現直接排下去會變成Impossible:

事實上這題並不是Impossible，研究一下發現至少要留兩格不排:

必須排在綠色的地方，如果排不下，則Impossible:


AC code:
http://ideone.com/sSwi90

#include<bits/stdc++.h>

using namespace std;

//印出盤面

void print(int r,int c,char data[60][60])

{

        for(int i=0;i<r;i++)

        {

                for(int j=0;j<c;j++)

                {

                        cout<<data[i][j];

                }

                cout<<endl;

        }

}

//算某個點的上下左右邊位置

vector<pair<int,int> > get8side(int i,int j,int r,int c)

{

        vector<pair<int,int> > sides;

        if(i!=0)

                sides.push_back(make_pair(i-1,j));

        if(j!=0)

                sides.push_back(make_pair(i,j-1));

        if(i<r-1)

                sides.push_back(make_pair(i+1,j));

        if(j<c-1)

                sides.push_back(make_pair(i,j+1));

        if(i!=0 && j!=0)

                sides.push_back(make_pair(i-1,j-1));

        if(i!=0 && j<c-1)

                sides.push_back(make_pair(i-1,j+1));

        if(i<r-1 && j!=0)

                sides.push_back(make_pair(i+1,j-1));

        if(i<r-1 && j<c-1)

                sides.push_back(make_pair(i+1,j+1));

        return sides;

}

//確認這一點的數字是不是0

bool checkZero(int i,int j,int r,int c,char data[60][60])

{

        if(data[i][j]=='*')

                return false;

        vector<pair<int,int> > side=get8side(i,j,r,c);

        for(int i=0;i<side.size();i++)

        {

                if(data[side[i].first][side[i].second]=='*')

                        return 0;

        }

        return true;

}

void dfs(int i,int j,int r,int c,char data[60][60],bool visit[60][60])

{

        if(visit[i][j]==1) return;

        visit[i][j]=1;

        if(!checkZero(i,j,r,c,data)) return;

        vector<pair<int,int> > side=get8side(i,j,r,c);

        for(vector<pair<int,int> >::iterator iter=side.begin();iter!=side.end();iter++)

        {

                dfs(iter->first,iter->second,r,c,data,visit);

        }

}

//確認盤面是否合理

bool check(int r,int c,char data[60][60])

{

        bool visit[60][60]={0};

        for(int i2=0;i2<r;i2++)

                for(int j2=0;j2<c;j2++)

                        if(data[i2][j2]=='c')

                        {

                                dfs(i2,j2,r,c,data,visit);

                                for(int i=0;i<r;i++)

                                        for(int j=0;j<c;j++)

                                        {

                                                if(data[i][j]!='*' && visit[i][j]==0){

                                                        return false;

                                                }

                                        }

                                return true;

                        }

}

int main()

{

        int T,no=1;

        cin>>T;

        int r,c,m;

        char data[60][60];

        while(T--)

        {

                cin>>r>>c>>m;

                cout<<"Case #"<<no++<<": "<<endl;

                memset(data,'.',sizeof data);

                data[0][0]='c';

                int lr=r-1,lc=c-1;//右下角還沒擺地雷的那個點的座標

                //用while迴圈持續放地雷，m帶表剩下的地雷數

                while(1)

                {

                        if(m==0) //全部擺完

                        {

                                if(check(r,c,data))

                                        print(r,c,data);

                                else

                                        cout<<"Impossible\n";

                                break;

                        }

                        else if(m<lr+1 && m<lc+1) //無法擺滿一行

                        {

                                if(lr+lc-3>=m){

                                        for(int i=lc;i>=2;i--){

                                                if(m==0)break;

                                                data[lr][i]='*';

                                                m--;

                                        }

                                        for(int i=lr-1;i>=2;i--){

                                                if(m==0)break;

                                                data[i][lc]='*';

                                                m--;

                                        }

                                        if(check(r,c,data))

                                                print(r,c,data);

                                        else

                                                cout<<"Impossible\n";

                                }

                                else

                                        cout<<"Impossible\n";

                                break;

                        }

                        //擺右邊及擺下面

                        else if(lc>lr)

                        {

                                for(int i=0;i<=lr;i++){

                                        data[i][lc]='*';

                                        m--;

                                }

                                lc--;

                        }

                        else

                        {

                                for(int i=0;i<=lc;i++){

                                        data[lr][i]='*';

                                        m--;

                                }

                                lr--;

                        }

                }

        }

}