アットウィキロゴ

全体公開 > 合同練習会 > 20130323 > L 平面上の蛇

問題の概要

01のグリッドがある.
1の列であり, 列の最初と最後以外はちょうど2つ1と接しているようなものを蛇と言う.
つまり, 分岐がなく, 環状でもない列で, 周りが0なものである.
0を1に変える事で, 蛇を(他の蛇とくっつけずに)伸ばせないようなものを最大蛇という.
最大蛇の個数を数えよ.

実装の方針, 注意点

+ ...
連結成分毎に, 最大蛇であるか調べる.
デバッグの都合を考え, 最初に各連結成分に異なる整数を割り当てた. (バグが出なかったので必要無かったが.)

蛇であるかは,
  • 1つ以下と接しているマスが1つか2つ. (これが頭になる.)
  • それ以外のマスは2つと接している.
の条件をチェックすればよい.

最大蛇であるかは, 頭の周りの空白マスを1にした時, それが頭の条件を満たすか否かをチェックすればよい.

ソースコード

+ ...
  1. typedef complex<int> P;
  2. #define X real()
  3. #define Y imag()
  4. P dirs[] = { P(1, 0), P(0, 1), P(-1, 0), P(0, -1), };
  5. namespace std{
  6. bool operator<(const P &p1, const P &p2) {
  7. return p1.X == p2.X ? p1.Y < p2.Y : p1.X < p2.X;
  8. }
  9. };
  10.  
  11. // pos と同じ色で連結している所を, color で塗る.
  12. set<P> coloring(vvi &in, P pos, int color){
  13. int bck = in[pos.X][pos.Y];
  14. in[pos.X][pos.Y] = color;
  15. set<P> res;
  16. res.insert(pos);
  17. rep(dir, 4){
  18. P npos = pos + dirs[dir];
  19. if(in[npos.X][npos.Y] == bck){
  20. set<P> tmp = coloring(in, npos, color);
  21. res.insert(all(tmp));
  22. }
  23. }
  24. return res;
  25. }
  26. bool is_maxsnake(vvi &in, set<P> &body){
  27. // 蛇かチェックし, 頭/尻尾を決める.
  28. vector<P> heads;
  29. foreach(it, body){
  30. int cnt = 0;
  31. rep(dir, 4) if(body.count(*it + dirs[dir])) ++cnt;
  32. if(cnt > 2) return false;
  33. if(cnt < 2) heads.pb(*it);
  34. }
  35. if(sz(heads) >= 3 || sz(heads) == 0) return false;
  36.  
  37. // 蛇が最大であるかチェックする.
  38. repsz(i, heads) rep(dir, 4){
  39. P nei = heads[i] + dirs[dir];
  40. if(in[nei.X][nei.Y] == 0){
  41. int cnt = 0;
  42. rep(dir2, 4)
  43. if(in[(nei+dirs[dir2]).X][(nei+dirs[dir2]).Y] > 0) ++cnt;
  44. if(cnt == 1) return false;
  45. }
  46. }
  47. return true;
  48. }
  49. /*
  50. void output(const vvi &in){
  51.   repsz(i, in){
  52.   repsz(j, in[i]){
  53.   cout << setw(3) << in[i][j];
  54.   }
  55.   cout << endl;
  56.   }
  57.   cout << endl;
  58. }
  59. */
  60. bool solve(){
  61. int h, w;
  62. cin >> h >> w;
  63. if(!(h|w)) return false;
  64.  
  65. // 周りは -1 で囲う.
  66. vvi in(h+2, vi(w+2, -1));
  67. rep(i, h) rep(j, w){
  68. char c; cin >> c;
  69. in[i+1][j+1] = c - '0';
  70. }
  71. h += 2; w += 2;
  72.  
  73. int color = 2;
  74. vector<set<P> > connects;
  75. rep(i, h) rep(j, w) if(in[i][j] == 1){
  76. connects.pb(coloring(in, P(i, j), color++));
  77. }
  78.  
  79. // output(in);
  80. int res = 0;
  81. repsz(i, connects) if(is_maxsnake(in, connects[i])) ++res;
  82. cout << res << endl;
  83. return true;
  84. }
  85.  



最終更新:2013年03月27日 02:17