Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2406-1612f20e
この記事にトラックバックする(FC2ブログユーザー)

SRM563 DIV2 MEDIUM - CoinsGameEasy (この記事を編集する[管理者用])

Source

TopCoder SRM563 DIV2 MEDIUM (550pt)
Problem Statement

問題概要

20*20以下のグリッドが与えられる.各セルは空かコインか障害物がおいてある.
コインの数はちょうど2個.
グリッドを上下左右に一瞬傾けるという操作を行うことができる.そうすると,
 すべてのコインが傾けた向きに1だけ移動する
 ただし,移動先が障害物なら現在の位置に残る
 また,移動先がグリッドの外ならグリッドから落ちてコインがなくなる
いくらか操作した後,1枚のコインが落ちて,1枚のコインがグリッドに残ってなければいけない.
そういう操作の回数の最小値を求める問題.操作の回数が11以上必要,もしくは,不可能なら-1を返す.

解法

各コインがどこにあるかを状態としてBFSする.
4^10通り全部動かし方を試しても良い.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

class CoinsGameEasy {
public:
int minimalSteps(vector <string> mp) {
  int i, j, k, d;
  int x, y, xy;
  int x1, y1, x2, y2, xy1, xy2;
  int nx1, ny1, nx2, ny2, nxy1, nxy2;
  int fall;
  int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1};
  static int dist[1000][1000], q[1000000], q_st, q_size;

  x = mp.size();
  y = mp[0].size();
  xy = x*y;

  k = 0;
  rep(i,x) rep(j,y) if(mp[i][j]=='o'){
    if(k==0) x1 = i, y1 = j, xy1 = x1 * y + y1;
    if(k==1) x2 = i, y2 = j, xy2 = x2 * y + y2;
    k++;
    mp[i][j] = '.';
  }

  rep(i,xy) rep(j,xy) dist[i][j] = -1;

  q_st = q_size = 0;
  q[q_st+q_size++] = xy1 * xy + xy2;
  dist[xy1][xy2] = 0;

  while(q_size){
    xy1 = q[q_st] / xy;
    xy2 = q[q_st] % xy;
    q_st++; q_size--;
    x1 = xy1 / y; y1 = xy1 % y;
    x2 = xy2 / y; y2 = xy2 % y;

    if(dist[xy1][xy2]==10) break;

    rep(d,4){
      nx1 = x1 + dx[d]; ny1 = y1 + dy[d];
      nx2 = x2 + dx[d]; ny2 = y2 + dy[d];
      fall = 0;
      if(nx1 < 0 || ny1 < 0 || nx1 >= x || ny1 >= y) fall |= 1;
      if(nx2 < 0 || ny2 < 0 || nx2 >= x || ny2 >= y) fall |= 2;
      if(fall==1||fall==2) return dist[xy1][xy2] + 1;
      if(fall==3) continue;
      if(mp[nx1][ny1]=='#') nx1 = x1, ny1 = y1;
      if(mp[nx2][ny2]=='#') nx2 = x2, ny2 = y2;

      nxy1 = nx1 * y + ny1;
      nxy2 = nx2 * y + ny2;
      if(dist[nxy1][nxy2]>=0) continue;
      dist[nxy1][nxy2] = dist[xy1][xy2] + 1;
      q[q_st+q_size++] = nxy1 * xy + nxy2;
    }
  }

  return -1;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2406-1612f20e
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。