GCJ2014 problemC (fails)

gistfile1.cpp

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <fstream>
#include <cassert>

using namespace std;

vector<string> split(const string _s, const string del);
vector<int> loadFromLine(ifstream& file);
int toInt(string s) { int r = 0; istringstream ss(s); ss >> r; return r; }
string toStr(int n) { ostringstream ss; ss << n; return ss.str(); }
string cToStr(char c) { ostringstream ss; ss << c; return ss.str(); }

void markNearMine(int row, int col, char** board, int board_row, int board_col){
    for(int dr=-1; dr<=1; dr++){
        for(int dc=-1; dc<=1; dc++){
            int rpos = row+dr;
            int cpos = col+dc;

            if(rpos < 0 || rpos >= board_row) continue;
            if(cpos < 0 || cpos >= board_col) continue;
            if (board[rpos][cpos] == '*'){ board[row][col] = 'x'; break; }
        }
    }
}

void openZeros(int row, int col, char** board, int board_row, int board_col){
    if(board[row][col] == 'x') { board[row][col] = 'y'; return; }
    if(board[row][col] != 'c') board[row][col] = 'y';

    for(int dr=-1; dr<=1; dr++){
        for(int dc=-1; dc<=1; dc++){
            int rpos = row+dr;
            int cpos = col+dc;

            if(rpos < 0 || rpos >= board_row) continue;
            if(cpos < 0 || cpos >= board_col) continue;

            if(board[rpos][cpos] == '.' || board[rpos][cpos] == 'x') openZeros(rpos,cpos,board,board_row,board_col);
        }
    }
    return;
}

string printBoard(char** board, int rows, int cols){
    string str = "";
    for(int r=0; r<rows; r++){
        for(int c=0; c<cols; c++){
            str += cToStr(board[r][c]);
        }
        if(r < rows-1) str += "\n";
    }
    return str;
}

bool isPossible(char** board, int board_row, int board_col){
    // open closed only once
    int r,c;
    for(r=0; r<board_row; r++){
        for(c=0; c<board_col; c++){
            if(board[r][c] == '.'){
                board[r][c] = 'c';
                openZeros(r, c, board, board_row, board_col);
                break;
            }
        }
        if(board[r][c] == 'c') break;
    }
    // final check
    //cout << endl << printBoard(board, board_row, board_col) << endl;
    for(int r=0; r<board_row; r++){
        for(int c=0; c<board_col; c++){
            if(board[r][c] == '.' || board[r][c] == 'x') return false;
            if(board[r][c] == 'y') board[r][c] = '.';
        }
    }

    return true;
}

void setMines(int mines, char** board, int board_rows, int board_cols, int type){
    // init board
    for(int r=0; r<board_rows; r++){
        for(int c=0; c<board_cols; c++){
            board[r][c] = '.';
        }
    }

    switch(type){
        case 0:
            {
                int maxrow = board_rows-1;
                int maxcol = board_cols-1;
                int minrow = 0;
                int mincol = 0;
                int r,c;
                while(mines > 0){
                    for(r=minrow,c=mincol; c<=maxcol && mines > 0; c++){
                        if(board[r][c] != '*'){
                            board[r][c] = '*'; mines--;
                        }
                    }
                    for(r=minrow,c=maxcol; r<=maxrow && mines > 0; r++){
                        if(board[r][c] != '*'){
                            board[r][c] = '*'; mines--;
                        }
                    }
                    for(r=maxrow,c=maxcol; c>=mincol && mines > 0; c--){
                        if(board[r][c] != '*'){
                            board[r][c] = '*'; mines--;
                        }
                    }
                    for(r=maxrow,c=mincol; r>=minrow && mines > 0; r--){
                        if(board[r][c] != '*'){
                            board[r][c] = '*'; mines--;
                        }
                    }
                    maxcol -=1;
                    maxrow -=1;
                    mincol +=1;
                    minrow +=1;
                }
            }
            break;
        case 1:
            {
                for(int r=0; r<board_rows && mines > 0; r++){
                    for(int c=0; c<board_cols && mines > 0; c++){
                        board[r][c] = '*';
                        mines --;
                    }
                }
            }
            break;
        case 2:
            {
                for(int c=0; c<board_cols && mines > 0; c++){
                    for(int r=0; r<board_rows && mines > 0; r++){
                        board[r][c] = '*';
                        mines --;
                    }
                }
            }
            break;
        case 3:
            // TODO maxrow > maxcol ? check
            {
                int minrow = 0;
                int mincol = 0;
                while(mines > 0){
                    for(int c=mincol; c<board_cols && mines > 0; c++){
                        if(board[minrow][c] != '*'){
                            board[minrow][c] = '*'; mines--;
                        }
                    }
                    for(int r=minrow; r<board_rows && mines > 0; r++){
                        if(board[r][mincol] != '*'){
                            board[r][mincol] = '*'; mines--;
                        }
                    }
                    minrow += 1;
                    mincol += 1;
                }
            }
            break;
        case 4:
            {
                int minrow = 0;
                int mincol = 0;
                while(mines > 0){
                    for(int r=minrow; r<board_rows && mines > 0; r++){
                        if(board[r][mincol] != '*'){
                            board[r][mincol] = '*'; mines--;
                        }
                    }
                    for(int c=mincol; c<board_cols && mines > 0; c++){
                        if(board[minrow][c] != '*'){
                            board[minrow][c] = '*'; mines--;
                        }
                    }
                    minrow += 1;
                    mincol += 1;
                }
            }
            break;
        case 5: // corners
            {
                int minrow=0;
                int mincol=0;
                int maxrow = board_rows-1;
                int maxcol=board_cols-1;
                if(board[minrow][mincol] != '*' && mines > 0){ board[minrow][mincol] = '*'; mines--; }
                if(board[minrow][maxcol] != '*' && mines > 0){ board[minrow][maxcol] = '*'; mines--; }
                if(board[maxrow][maxcol] != '*' && mines > 0){ board[maxrow][maxcol] = '*'; mines--; }
                if(board[maxrow][mincol] != '*' && mines > 0){ board[maxrow][mincol] = '*'; mines--; }
            }
            break;
    }

    // markNearMine -> x
    for(int r=0;r<board_rows;r++){
        for(int c=0;c<board_cols;c++){
            if(board[r][c] == '.'){
                markNearMine(r,c,board,board_rows,board_cols);
            }
        }
    }
    // TODO
    //cout << "\n" << printBoard(board, board_rows, board_cols) << endl;
}

string solve(vector<int> inputs)
{
    const int ROWS = inputs[0];
    const int COLS = inputs[1];
    const int MINES = inputs[2];
    if( MINES >= ROWS*COLS ) return "Impossible";

    // allocation
    char** board = new char*[ROWS];
    for(int r=0; r<ROWS; r++){
        board[r] = new char[COLS];
    }

    // special case
    if( MINES == ROWS*COLS - 1 ){
        for(int r=0; r<ROWS; r++){
            for(int c=0; c<COLS; c++){
                board[r][c] = '*';
            }
        }
        board[0][0] = 'c';
        return printBoard(board, ROWS, COLS);
    }

    // special case 2 2x2 block
    if( ROWS*COLS-MINES == 4 && (ROWS > 1 && COLS > 1) ){
        for(int r=0; r<ROWS; r++){
            for(int c=0; c<COLS; c++){
                if(r<2 && c<2) {
                    board[r][c] = '.';
                } else {
                    board[r][c] = '*';
                }
            }
        }
        board[0][0] = 'c';
        return printBoard(board, ROWS, COLS);
    }

    // set Mines at Edges
    for(int type=0; type<=5; type++){
        if(type==5 && MINES > 4) break;

        setMines(MINES, board, ROWS, COLS, type);
        if( isPossible(board, ROWS, COLS) ) return printBoard(board, ROWS, COLS);
    }

    return printBoard(board, ROWS, COLS);
   // return "Impossible";
}

int main(int argc, char ** argv)
{
    assert(argc==2 && "Usage ./a.out <input file name>");

    ifstream file(argv[1]);
    int CASE_NUM = loadFromLine(file)[0];

    for (int lineNum = 0; lineNum<CASE_NUM; lineNum++)
    {
        vector<int> inputs;
        inputs = loadFromLine(file);

        string result = solve(inputs);

        cout << "Case #" << lineNum+1 << ":" << endl;
        cout << result << endl;
    }

    return 0;
}

vector <string> split(const string _s, const string del)
{
    vector <string> ret;
    string s = _s;

    while (!s.empty())
    {
        size_t pos = s.find(del);
        string sub = "";
        sub = s.substr(0, pos);
        ret.push_back(sub);
        if (pos != string::npos)
        pos += del.size();
        s.erase(0, pos);
    }

    return ret;
}

vector<int> loadFromLine(ifstream& file){
    string line;
    getline(file, line);
    vector<string> tmp  = split(line, " ");
    vector<int> args;
    for (uint i=0; i<tmp.size(); i++) args.push_back(toInt(tmp[i]));
    return args;
}