USACO 2.1 The Castle (castle)

//Main Idea 
//We use DFS to find the number of room and module_info[MAX][MAX]
//to record the visited info and then the room the module belong to;

/*
ID: haolink1
PROG: castle
LANG: C++
*/

//#include <iostream>
#include <fstream>

using namespace std;

const short MAX = 50;
//Record the visited info and then the room the module belong to;
short module_info[MAX][MAX];
//
short room_size[MAX*MAX] = {0};
//Record the wall info.
bool no_walls[MAX][MAX][4];
short room_num = 0;
short room_size_counter = 0;
void DFS(short row,short column);
class Solution{
public:
    short row_;
    short column_;
    short max_size;
    char direction;
    Solution(){
        row_ = -1;
        column_ = -1;
        max_size = 0;
        direction = ‘ ‘;
    }
};

int main(){
    ifstream fin("castle.in");
    short column = 0;
    short row = 0;
    fin >> column;
    fin >> row;
    short walls_info = 0;
    for(short i = 0; i < row; i++){
        for(short j = 0; j < column; j++){
            fin >> walls_info;
            //Note:We should take care the map between the num and the wall
            //and look the in binary form which is useful to retrieve the wall info.
            //Eg: 1,2,4,8 their binary form is 0001,0010,0100,1000, we can use & operator 
            //to retrieve the wall info.
            if( !(walls_info & 1))//no west wall
                no_walls[i][j][0] = true;
            if(!(walls_info & 2))//no north wall
                no_walls[i][j][1] = true;
            if(!(walls_info & 4))//no east wall
                no_walls[i][j][2] = true;
            if(!(walls_info & 8))//no south wall
                no_walls[i][j][3] = true;

//            if(walls_info%2 == 0) //To west
//                no_walls[i][j][0] = true;
//            if(walls_info!=2 && walls_info !=3 && walls_info !=6 && walls_info!=7 && walls_info!=10 &&
//                walls_info!=11 && walls_info!=14 && walls_info!=15)//To north
//                no_walls[i][j][1] = true;
//            if(walls_info!=4 && walls_info!=5 && walls_info!=6 && walls_info!=7 && walls_info < 12)//To east
//                no_walls[i][j][2] = true;
//            if(walls_info < 8)//To south
//                no_walls[i][j][3] = true;
            
            //Initialization. -1 mean the module haven‘t been visited;
            module_info[i][j] = -1;
        }
    }
    for(short i = 0; i < row; i++){
        for(short j = 0; j < column; j++){
            DFS(i,j);
            if(room_size_counter > 0){
                room_size[room_num] = room_size_counter;
                room_num++;
                room_size_counter = 0;
            }
        }
    }
    ofstream fout("castle.out");
    //Room num
    fout << room_num <<endl;
    //Max size room
    short max_size = 0;
    for(short i = 0; i < room_num; i++){
        if(room_size[i] > max_size) 
            max_size = room_size[i];
    }
    fout << max_size <<endl;
    //find the optimal wall to remove 
    Solution solution;
    //First find the most north, then the most east, we traverse all modules one by one.
    //This is the easiest way to implement to find the optimal wall to remove.
    for(short j = 0; j < column; j++){
        for(short i = row-1; i >= 0; i--){
            short temp_size = 0;
            if(i > 0 && no_walls[i][j][1] == false && module_info[i][j] != module_info[i-1][j]){//Check North
                temp_size =room_size[module_info[i][j]] + room_size[module_info[i-1][j]]; 
                if(temp_size > solution.max_size){
                    solution.max_size = temp_size;
                    solution.row_ = i;
                    solution.column_ = j;
                    solution.direction = ‘N‘;
                }
            }
            if(j < column-1 && no_walls[i][j][2] == false && module_info[i][j] != module_info[i][j+1]){//Check East
                temp_size = room_size[module_info[i][j]] + room_size[module_info[i][j+1]];  
                if(temp_size > solution.max_size){
                    solution.max_size = temp_size;
                    solution.row_ = i;
                    solution.column_ = j;
                    solution.direction = ‘E‘;
                }
            }
        }
    }

    fout << solution.max_size <<endl;
    fout << solution.row_+1 <<" "<< solution.column_+1<<" "<<solution.direction<<endl;
    return 0;
}

void DFS(short row,short column){
    if(module_info[row][column] != -1)
        return;
    //Keep the room which the module belong to;
    module_info[row][column] = room_num;
    room_size_counter++;
    if(no_walls[row][column][0] == true)
       DFS(row,column-1); 
    if(no_walls[row][column][1] == true)
        DFS(row-1,column);
    if(no_walls[row][column][2] == true)
        DFS(row,column+1);
    if(no_walls[row][column][3] == true)
        DFS(row+1,column);
}

USACO 2.1 The Castle (castle)

原文：http://blog.csdn.net/damonhao/article/details/19684427