アットウィキロゴ

全体公開 > 合同練習会 > 20130323 > I 彫像

問題の概要

8*8のボードの左下に居る8近傍に動けるMが, 右上を目指す.
ボードには彫像がいくつかあり, Mが動くと共に, 1だけ下に動く(一番下からは消える).
Mは, 彫像の居るマスには動けず, また, 彫像が上から来ると死ぬ.
右上に行けるか.

実装の方針, 注意点

+ ...
kターン目(0-base)にpに彫像があるか <=> 0ターン目に, pから上kマス行った所に彫像があるか
に注意する.
dp[ターン数][X座標][Y座標]=そのターンその場所に行けるか なる配列を用いた.
7ターン目に生き残っていればOKだが, OKなら, どうせ30ターンもすれば, 右上まで辿り着くので, 適当にターンを回しておく.

配列を使いまわし, メモリ使用量を O(盤面の大きさ^2 * ターン数) から O(盤面の大きさ^2) にする事も可能だが, そこまでする必要は無い.

ソースコード

+ ...
  1. typedef complex<int> P;
  2. P dirs[] = {
  3. P(0, 0),
  4. P(1, 0), P(0, 1), P(-1, 0), P(0, -1),
  5. P(1, 1), P(1,-1), P(-1, 1), P(-1, -1),
  6. };
  7. #define X real()
  8. #define Y imag()
  9. namespace std{
  10. bool operator<(const P &a, const P &b){
  11. return a.X == b.X ? a.Y < b.Y : a.X < b.X;
  12. }
  13. };
  14. bool inBoard(P p){
  15. return 0 <= p.X && p.X < 8 &&
  16. 0 <= p.Y && p.Y < 8;
  17. }
  18. bool solve(){
  19. set<P> statue;
  20. rep(i, 8){
  21. rep(j, 8){
  22. char c; cin >> c;
  23. if(c == 'S') statue.insert(P(i, j));
  24. }
  25. }
  26.  
  27. vector<vvi> dp(40);
  28. repsz(i, dp) dp[i] = vvi(8, vi(8));
  29. dp[0][7][0] = 1;
  30. rep(turn, sz(dp)-1){
  31. rep(i, 8) rep(j, 8) if(dp[turn][i][j]){
  32. rep(dir, 9){
  33. P np = P(i, j) + dirs[dir];
  34. if(!inBoard(np)) continue;
  35. if(statue.count(np - P(turn, 0))) continue;
  36. if(statue.count(np - P(turn+1, 0))) continue;
  37. dp[turn+1][np.X][np.Y] = 1;
  38. }
  39. }
  40. }
  41. if(dp[sz(dp)-1][0][7]){
  42. cout << "WIN" << endl;
  43. }else{
  44. cout << "LOSE" << endl;
  45. }
  46. return true;
  47. }
  48.  



最終更新:2013年03月27日 01:00