问题来源: http://www.blogjava.net/sandy/archive/2013/04/15/397875.html
问题: 给定一个2D的棋盘, 含有'X'和'O', 找到所有被'X'包围的'O', 然后把该区域的'O'都变成'X'
#include <cstdio>
#include <fstream>
enum FLAG
{
X = 'X',
O = 'O'
};
enum STATE
{
DANGER,
SAFETY,
UNKNOWN
};
class Game
{
public:
Game();
~Game();
public:
bool init(const char * file);
void solve_way_1();
void roll_back();
void solve_way_2();
void show(bool before);
private:
bool create_status(int row_num, int col_num);
void clear_status();
bool load_status(std::ifstream & ifs);
STATE solve_one_way_1(int row, int col);
void solve_one_way_2(int row, int col);
private:
Game(const Game &);
Game & operator = (const Game &);
private:
struct STATUS
{
FLAG bef_flag;
FLAG aft_flag;
STATE state;
};
private:
int m_row;
int m_col;
int m_row_max;
int m_col_max;
STATUS ** m_status;
};
Game::Game()
: m_status(NULL)
, m_row(0)
, m_col(0)
, m_row_max(0)
, m_col_max(0)
{
}
Game::~Game()
{
clear_status();
}
bool Game::init(const char * file)
{
if (NULL == file)
{
return(false);
}
std::ifstream ifs(file);
if (!ifs.is_open())
{
return(false);
}
int row_num = 0;
int col_num = 0;
ifs >> row_num;
ifs >> col_num;
if (0 >= row_num || 0 >= col_num)
{
return(false);
}
if (row_num <= m_row_max && col_num <= m_col_max)
{
m_row = row_num;
m_col = col_num;
}
else
{
clear_status();
if (!create_status(row_num, col_num))
{
return(false);
}
}
return(load_status(ifs));
}
bool Game::create_status(int row_num, int col_num)
{
typedef STATUS * PSTATUS;
m_status = new PSTATUS[row_num];
if (NULL == m_status)
{
return(false);
}
m_col = col_num;
m_col_max = col_num;
for (m_row = 0; m_row < row_num; ++m_row)
{
m_status[m_row] = new STATUS[col_num];
if (NULL == m_status[m_row])
{
break;
}
}
m_row_max = m_row;
return(m_row == row_num);
}
void Game::clear_status()
{
for (int row = 0; row < m_row_max; ++row)
{
delete [] m_status[row];
}
delete [] m_status;
m_row = 0;
m_col = 0;
m_row_max = 0;
m_col_max = 0;
}
bool Game::load_status(std::ifstream & ifs)
{
for (int row = 0; row < m_row; ++row)
{
for (int col = 0; col < m_col; ++col)
{
STATUS & status = m_status[row][col];
char flag = '\0';
ifs >> flag;
if (X == flag)
{
status.bef_flag = X;
status.aft_flag = X;
status.state = DANGER;
}
else if (O == flag)
{
status.bef_flag = O;
status.aft_flag = O;
status.state = UNKNOWN;
}
else
{
return(false);
}
}
}
return(ifs.good());
}
STATE Game::solve_one_way_1(int row, int col)
{
STATE & state = m_status[row][col].state;
if (UNKNOWN != state)
{
return(state);
}
FLAG & flag = m_status[row][col].aft_flag;
if (0 == row || m_row - 1 == row ||
0 == col || m_col - 1 == col ||
SAFETY == m_status[row - 1][col].state ||
SAFETY == m_status[row][col - 1].state ||
SAFETY == solve_one_way_1(row, col + 1) ||
SAFETY == solve_one_way_1(row + 1, col))
{
state = SAFETY;
flag = O;
}
else
{
state = DANGER;
flag = X;
}
return(state);
}
void Game::solve_way_1()
{
for (int row = 0; row < m_row; ++row)
{
for (int col = 0; col < m_col; ++col)
{
solve_one_way_1(row, col);
}
}
}
void Game::roll_back()
{
for (int row = 0; row < m_row; ++row)
{
for (int col = 0; col < m_col; ++col)
{
STATUS & status = m_status[row][col];
if (O == status.bef_flag)
{
status.aft_flag = O;
status.state = UNKNOWN;
}
}
}
}
void Game::solve_one_way_2(int row, int col)
{
if (0 > row || 0 > col || row >= m_row || col >= m_col)
{
return;
}
if (X == m_status[row][col].bef_flag ||
SAFETY == m_status[row][col].state)
{
return;
}
m_status[row][col].state = SAFETY;
solve_one_way_2(row - 1, col);
solve_one_way_2(row, col - 1);
solve_one_way_2(row + 1, col);
solve_one_way_2(row, col + 1);
}
void Game::solve_way_2()
{
for (int col = 0; col < m_col; ++col)
{
if (O == m_status[0][col].bef_flag)
{
m_status[0][col].state = SAFETY;
solve_one_way_2(1, col);
}
if (O == m_status[m_row - 1][col].bef_flag)
{
m_status[m_row - 1][col].state = SAFETY;
solve_one_way_2(m_row - 2, col);
}
}
for (int row = 1; row < m_row - 1; ++row)
{
if (O == m_status[row][0].bef_flag)
{
m_status[row][0].state = SAFETY;
solve_one_way_2(row, 1);
}
if (O == m_status[row][m_col - 1].bef_flag)
{
m_status[row][m_col - 1].state = SAFETY;
solve_one_way_2(row, m_col - 2);
}
}
for (int row = 0; row < m_row; ++row)
{
for (int col = 0; col < m_col; ++col)
{
if (UNKNOWN == m_status[row][col].state)
{
m_status[row][col].aft_flag = X;
}
}
}
}
void Game::show(bool before)
{
printf("--- %s ---\n", before ? "before" : "after ");
for (int row = 0; row < m_row; ++row)
{
for (int col = 0; col < m_col; ++col)
{
if (before)
{
printf("%c ", m_status[row][col].bef_flag);
}
else
{
printf("%c ", m_status[row][col].aft_flag);
}
}
printf("\n");
}
}
int main(int argc, char * argv[])
{
const char * file = "graph.txt";
Game game;
game.init(file);
printf("\n- way 1 -\n");
game.solve_way_1();
game.show(true);
game.show(false);
game.roll_back();
printf("\n- way 2 -\n");
game.solve_way_2();
game.show(true);
game.show(false);
return(0);
}
数据:
4 4 X X X X X O O X O X O X O O X O
结果:
- way 1 - --- before --- X X X X X O O X O X O X O O X O --- after --- X X X X X X X X O X X X O O X O - way 2 - --- before --- X X X X X O O X O X O X O O X O --- after --- X X X X X X X X O X X X O O X O
我也写复杂了...