POJ 1175 - Starry Night

http://poj.org/problem?id=1175

概要

\(W \times H\) の 0, 1 からなるグリッドが与えられ、1 はそこに星があることを表す。 水平方向、垂直方向、あるいは対角線方向に隣接しているような空でない星の集まりを cluster と呼ぶ。

ある cluster 同士が similar とは、星の数が同じであり、向きを無視した場合の形が同じであるようなものを言う。 一般に、1つの cluster について8種類の向きが考えられる (figure 1)。

similar な cluster には同じ名前をつけるようにして、すべての cluster に名前をつけたものを答える。 名前とは小文字のアルファベット1文字で、左上から順に a, b, ... とつける。

制約

解法

がんばって実装するだけ。 cluster は set で座標の集合として表現した。

  1 #include <iostream>
  2 #include <vector>
  3 #include <queue>
  4 #include <algorithm>
  5 #include <iterator>
  6 #include <set>
  7 using namespace std;
  8 
  9 static const char MARKED = '!';
 10 
 11 set<pair<int,int> > rot(const set<pair<int,int> >& v, int H)
 12 {
 13   set<pair<int,int> > ret;
 14   for (set<pair<int,int> >::const_iterator it = v.begin(); it != v.end(); ++it) {
 15     ret.insert(make_pair(it->second, H - it->first - 1));
 16   }
 17   return ret;
 18 }
 19 
 20 set<pair<int,int> > rev(const set<pair<int,int> >& v, int W)
 21 {
 22   set<pair<int,int> > ret;
 23   for (set<pair<int,int> >::const_iterator it = v.begin(); it != v.end(); ++it) {
 24     ret.insert(make_pair(it->first, W - it->second - 1));
 25   }
 26   return ret;
 27 }
 28 
 29 struct cluster
 30 {
 31   char name;
 32   int i, j;
 33   int W, H;
 34   set<pair<int,int> > v;
 35 
 36   bool same(const cluster& c) const
 37   {
 38     if ((H == c.H && W == c.W) || (H == c.W && W == c.H)) {
 39       set<pair<int,int> > tmp(v);
 40       int h = H, w = W;
 41       for (int k = 0; k < 4; k++) {
 42         if (h == c.H && w == c.W && tmp == c.v) {
 43           return true;
 44         }
 45         tmp = rot(tmp, h);
 46         swap(h, w);
 47       }
 48       tmp = rev(tmp, w);
 49       for (int k = 0; k < 4; k++) {
 50         if (h == c.H && w == c.W && tmp == c.v) {
 51           return true;
 52         }
 53         tmp = rot(tmp, h);
 54         swap(h, w);
 55       }
 56       return false;
 57     } else {
 58       return false;
 59     }
 60   }
 61 
 62   void paint(vector<string>& grid) const
 63   {
 64     for (set<pair<int,int> >::const_iterator it = v.begin(); it != v.end(); ++it) {
 65       grid[i+it->first][j+it->second] = name;
 66     }
 67   }
 68 };
 69 
 70 cluster find_cluster(vector<string>& grid, int start_i, int start_j)
 71 {
 72   const int H = grid.size(), W = grid[0].size();
 73   queue<pair<int,int> > q;
 74   q.push(make_pair(start_i, start_j));
 75   grid[start_i][start_j] = MARKED;
 76   int top = start_i, bottom = start_i, left = start_j, right = start_j;
 77   set<pair<int,int> > v;
 78   while (!q.empty()) {
 79     const pair<int,int> p = q.front();
 80     q.pop();
 81     v.insert(p);
 82     for (int d = 0; d < 8; d++) {
 83       static const int di[] = {-1, -1, 0, 1, 1, 1, 0, -1};
 84       static const int dj[] = {0, 1, 1, 1, 0, -1, -1, -1};
 85       const int i = p.first + di[d];
 86       const int j = p.second + dj[d];
 87       if (0 <= i && i < H && 0 <= j && j < W && grid[i][j] == '1') {
 88         grid[i][j] = MARKED;
 89         q.push(make_pair(i, j));
 90         top = min(top, i);
 91         bottom = max(bottom, i);
 92         left = min(left, j);
 93         right = max(right, j);
 94       }
 95     }
 96   }
 97   cluster c;
 98   c.i = top;
 99   c.j = left;
100   c.H = bottom - top + 1;
101   c.W = right - left + 1;
102   for (set<pair<int,int> >::iterator it = v.begin(); it != v.end(); ++it) {
103     c.v.insert(make_pair(it->first - c.i, it->second - c.j));
104   }
105   return c;
106 }
107 
108 int main()
109 {
110   ios::sync_with_stdio(false);
111   int W, H;
112   cin >> W >> H;
113   vector<string> grid(H);
114   for (int i = 0; i < H; i++) {
115     cin >> grid[i];
116   }
117 
118   char name = 'a';
119   vector<cluster> v;
120   for (int i = 0; i < H; i++) {
121     for (int j = 0; j < W; j++) {
122       if (grid[i][j] == '1') {
123         cluster c = find_cluster(grid, i, j);
124         c.name = name;
125         for (vector<cluster>::iterator it = v.begin(); it != v.end(); ++it) {
126           if (it->same(c)) {
127             c.name = it->name;
128             break;
129           }
130         }
131         if (c.name == name) {
132           ++name;
133           v.push_back(c);
134         }
135         c.paint(grid);
136       }
137     }
138   }
139 
140   copy(grid.begin(), grid.end(), ostream_iterator<string>(cout, "\n"));
141   return 0;
142 }
poj/1175.cc