Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-15

GeneralChess

| 18:47

問題文, SRM 197

Algorithm Tutorials -- How to Find a Solutionから。

全てのナイトから脅かされているマスの位置を探す。

219.34/250

class GeneralChess {
public:
    vector <string> attackPositions(vector <string> pieces) {
        const int n = pieces.size();
        map<pair<int,int>,int> count;
        for (int i = 0; i < n; i++) {
            int x, y;
            sscanf(pieces[i].c_str(), "%d,%d", &x, &y);
            for (int dx = -2; dx <= 2; dx++)
                for (int dy = -2; dy <= 2; dy++) {
                    if (dx*dx+dy*dy != 5) continue;
                    count[make_pair(x+dx,y+dy)]++;
                }
        }

        vector<string> result;
        for (map<pair<int,int>,int>::const_iterator itr = count.begin();
                itr != count.end(); itr++)
            if (itr->second == n) {
                ostringstream oss;
                oss << itr->first.first << ',' << itr->first.second;
                result.push_back(oss.str());
            }
        return result;
    }
};