SRM 593 Div1 L1:HexagonalBoard,用染色法判断无向图是否为二分图
题目来源:http://community.topcoder.com/stat?c=problem_statement&pm=12784最近由于考研,一个多月没有做TopCoder了,第一次参加Div1,结果第一题都没搞出来,看了社论之后学到了用DFS染色法判断无向图是否是二分图的方法。深刻感觉本人太水了,要加油!代码如下:#include#include#incl
·
题目来源:http://community.topcoder.com/stat?c=problem_statement&pm=12784
最近由于考研,一个多月没有做TopCoder了,第一次参加Div1,结果第一题都没搞出来,看了社论之后学到了用DFS染色法判断无向图是否是二分图的方法。深刻感觉本人太水了,要加油!
代码如下:
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
using namespace std;
/*************** Program Begin **********************/
int dx[] = {0, -1, -1, 0, 1, 1}, dy[] = {-1, 0, 1, 1, 0, -1};
class HexagonalBoard {
private:
vector <string> board;
int color[50][50];
int result, N;
public:
void DFS(int x, int y, int c)
{
int nx, ny;
if ('X' == board[x][y] && -1 == color[x][y]) {
color[x][y] = c;
result = max(result, 1);
for (int i = 0; i < 6; i++) {
nx = x + dx[i];
ny = y + dy[i];
if (nx < 0 || nx > N-1 || ny < 0 || ny > N-1) {
continue;
}
if ('X' == board[nx][ny]) {
result = max(result, 2);
DFS(nx, ny, !c);
if (c == color[nx][ny]) {
result = 3;
}
}
}
}
}
int minColors(vector <string> board)
{
this->board = board;
memset(color, -1, sizeof(color));
result = 0;
N = board.size();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
DFS(i, j, 0);
}
}
return result;
}
};
/************** Program End ************************/
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
已为社区贡献10条内容
所有评论(0)