Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-01

Quilting

| 11:24

問題文

キルト作り。自力で解けたが、解くのに一時間以上かかった。

class Quilting {
    public:
        string lastPatch(int length, int width, vector <string> colorList) {
            vector<vector<string> > quilt(200,vector<string>(200,string(".")));
            map<string,int> prevCount;
            int y=100, x=100, dir=0;
            quilt[y][x] = colorList[0];
            prevCount[colorList[0]]++;
            for (int i = 1; i < length*width; i++) {
                const static int NEIGHBORS = 8;
                const static int nd[NEIGHBORS][2] = {
                    {-1,-1}, {-1, 0}, {-1, 1},
                    { 0,-1},          { 0, 1},
                    { 1,-1}, { 1, 0}, { 1, 1} };
                const static int MOVE_KINDS = 4;
                const static int mvd[MOVE_KINDS][4] = {
                    {-1, 0, 0,-1}, { 0,-1, 1, 0},
                    { 1, 0, 0, 1}, { 0, 1,-1, 0} };
                y += mvd[dir][0];
                x += mvd[dir][1];
                map<string,int> neighorCount;
                for (int j = 0; j < NEIGHBORS; j++) {
                    const int dy = y + nd[j][0];
                    const int dx = x + nd[j][1];
                    if (quilt[dy][dx] != ".") {
                        neighorCount[quilt[dy][dx]]++;
                    }
                }
                string color;
                int minSameColor = INT_MAX;
                if (neighorCount.size() == colorList.size()) {
                    for (map<string,int>::const_iterator itr = neighorCount.begin();
                            itr != neighorCount.end(); itr++) {
                        if (itr->second < minSameColor) {
                            color = itr->first;
                            minSameColor = itr->second;
                        } else if (itr->second == minSameColor) {
                            if (prevCount[itr->first] < prevCount[color]) {
                                color = itr->first;
                            } else if (prevCount[itr->first] == prevCount[color]) {
                                if (find(colorList.begin(),colorList.end(),itr->first) 
                                        < find(colorList.begin(),colorList.end(),color)) {
                                    color = itr->first;
                                }
                            }
                        }
                    }
                } else {
                    for (int j = 0; j < colorList.size(); j++) {
                        if (neighorCount.find(colorList[j]) == neighorCount.end()) {
                            if (prevCount[colorList[j]] < minSameColor) {
                                minSameColor = prevCount[colorList[j]];
                                color = colorList[j];
                            }
                        }
                    }
                }
                quilt[y][x] = color;
                prevCount[color]++;
                if (quilt[y+mvd[dir][2]][x+mvd[dir][3]] == ".") {
                    dir = (dir+1) % MOVE_KINDS;
                }
            }
            return quilt[y][x];
        }
};