11520 Fill the Square

題目：http://luckycat.kshs.kh.edu.tw/homework/q11520.htm
觀念：greedy
難度：luckycat ★★

參考解答：
http://programming-study-notes.blogspot.tw/2014/01/uva-11520-fill-square.html

#include <bits/stdc++.h>
using namespace std;

char square[12][12];

void fillChar (int n,int i,int j){
    char filled = 'A';
    bool up,left,right,down;

    //嘗試A~Z之間的所有字母
    while (filled <= 'Z'){

        //此格的上下左右 '超過邊界' 或 '內容與此格不同'  
        if (i-1<0  || square[i-1][j]!=filled) up=1;   else up=0;
        if (i+1>=n || square[i+1][j]!=filled) down=1; else down=0;
        if (j-1<0  || square[i][j-1]!=filled) left=1; else left=0;
        if (j+1>=n || square[i][j+1]!=filled) right=1;else right=0;

        //四邊的格子都與本格不衝突的話，就可以使用所選的字母
        if (up && down && left && right){
            square[i][j] = filled;
            cout<<filled;
            break;
        }
        else filled += 1; //換成下一個字母，例如：A -> B
    }
}

int main()
{
    //t是測資數量，n是正方形的邊長
    int t,n,Case=1;
    cin>>t;
    while (t--)
    {
        cin>>n;
        gets(square[0]);
        for(int i=0;i<n;i++) gets(square[i]);

        cout<<"Case "<<Case++<<endl;

        //對每一個格子做greedy演算法
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if (square[i][j]!='.')
                {
                    //如果此格已經有字母則輸出
                    cout<<square[i][j];
                }                    
                else
                {
                    //還是空格子，決定該填上哪個字母
                    fillChar(n,i,j);
                }
            }
            cout<<endl;
        }
    }

    return 0;
}

Stanley 版解答 ：

#include <iostream>
#include <string.h>
using namespace std;

char  answer[12][12];

int T, N, c = 1, dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool findedAns;

bool check( int y , int x , char c ){

    for ( int d = 0 ; d < 4 ; d++ ){
        int ny = y + dy[d];
        int nx = x + dx[d];

        if ( nx >= 0 && nx < N && ny >= 0 && ny < N ){
            if ( answer[ny][nx] == c )
                return false;

        }


    }
    return true;
}

void Go( int y , int x ){

    if ( findedAns ) return;
    if ( x == N ){

        if ( y == N-1 ){

            cout << "Case " << c++  << ":"<< endl;
            for ( int i = 0 ; i < N ; i++ )
                cout << answer[i] << endl;

            findedAns = true;
            return;
        }
        else
            Go( y+1 , 0 );
    }
    else{

        if ( answer[y][x] != '.' )
            Go( y , x+1 );

        else{

            for ( char c = 'A' ; c <= 'Z' ; c++ )
                if ( check( y , x , c ) ){
                    answer[y][x] = c;
                    Go( y , x+1 );
                    answer[y][x] = '.';

                }
        }


    }



}

int main(){

    cin >> T;

    while ( T-- ){
        cin >> N;

        for ( int i = 0 ; i < N ; i++ )
            cin >> answer[i];

        findedAns = false;

        Go( 0 , 0 );



    }



    return 0;
}