Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2013-10-06

HexagonalBoard (SRM 593 Div1 Easy)

| 21:42 | HexagonalBoard (SRM 593 Div1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - HexagonalBoard (SRM 593 Div1 Easy) - TopCoder煮ブログ

方針は http://topcoder.g.hatena.ne.jp/nitoyon/20131005/1380995960 で固まっていたので、あとは書くだけ。

単純ミスで 1 回、System Test 落ちたあと、再提出で pass。ダメな感じ。

あと、最大 3 色だというところの証明がパッと出てこない。

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#define _USE_MATH_DEFINES
#include <math.h>
#include <string.h>
using namespace std;

// -xx
// x*x
// xx-
int neighbor[][2] = {{0,-1},{1,-1},{-1,0},{1,0},{-1,1},{0,1}};

class HexagonalBoard {
    bool visited[50][50];
    int color[50][50];
    vector<string> b;
    int N;
public:
    int search(int x, int y, int col) {
        visited[y][x] = true;
        color[y][x] = col;
        int ret = 1;
        for (int i = 0; i < 6; i++) {
            int xx = x + neighbor[i][0];
            int yy = y + neighbor[i][1];
            if (xx < 0 || yy < 0 || xx >= N || yy >= N) {
                continue;
            }
            if (b[yy][xx] == 'X') {
                ret = max(ret, 2);
                if (visited[yy][xx]) {
                    if (color[yy][xx] != -col) {
                        ret = 3;
                    }
                } else {
                    ret = max(ret, search(xx, yy, -col));
                }
            }
        }
        return ret;
    }

    int minColors(vector <string> board) {
        b = board;
        N = b.size();
        memset(visited, 0, sizeof(visited));
        memset(color, 0, sizeof(color));
        int ret = 0;

        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                if (b[y][x] == 'X' && !visited[y][x]) {
                    ret = max(ret, search(x, y, 1));
                }
            }
        }
        return ret;
    }
};