Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM498 DIV2 HARD - NinePuzzle (この記事を編集する[管理者用])

Source

TopCoder SRM498 DIV2 HARD (950pt)
Problem Statement

問題概要

問題の図のような10ピースのパズルを考える.1マス空いていて,そこに隣接するピースを移動できる.
各マスは4色 (赤,緑,青,黄) のどれかの色に塗られている.
初期状態と終了状態が与えられたとき,最小で何個のマスを塗り直せば終了状態に移動できるようになるか,を求める問題.

解法

実は全ての状態に遷移可能なので,同じ色を一致させて,残りを変換すれば良い.
状態数は高々10!で,色が4色しかないことからもっと少ないので,全状態を作って,何色違っているかのminを取るのも良い.(以下のコードはこれ)

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

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

int edge_baka[10][10]={
  {1,2},
  {0,2,3,4},
  {0,1,4,5},
  {1,4,6,7},
  {1,2,3,5,7,8},
  {2,4,8,9},
  {3,7},
  {3,4,6,8},
  {4,5,7,9},
  {5,8}
};

int edge[10][10];

string in, goal;
int res;
set<string> s;
int cnt=0;

void solve(void){
  int i,j,tmp,as;

  if(s.count(in)) return;
  s.insert(in);

  rep(i,10) if(in[i]=='*') break; as=i;

  tmp = 0;
  rep(i,10){
    if(in[i]==goal[i]) continue;
    if(in[i]=='*'){ tmp+=10000; break; }
    tmp++;
  }
  if(res > tmp) res = tmp;

  rep(i,10) if(edge[as][i]){
    swap(in[i],in[as]);
    solve();
    swap(in[i],in[as]);
  }
}

class NinePuzzle {
public:
int getMinimumCost(string init, string goal_baka) {
  int i,j;
  res = 10000;
  in = init;
  goal = goal_baka;
  s.clear();

  rep(i,10) rep(j,10) edge[i][j]=0;
  rep(i,10) rep(j,10){
    if(j-1>=0 && edge_baka[i][j] < edge_baka[i][j-1]) break;
    edge[i][edge_baka[i][j]]=1;
  }

  solve();
  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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