Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

February 2011 Challenge 6問目 - Rush Hour (この記事を編集する[管理者用])

Source

codechef February 2011 Challenge 6問目
Problem Statement
February 2011 Challengeの参加記録

問題概要

箱入り娘パズル.
12*12以下の盤面に,1*2または1*3または2*1または3*1の車が26種類以下配置されている.車にはユニークなアルファベットが割り当てられている.
aの車は横2マス,縦1マスであることが保証されている.
aの車を右端に移動するまでに必要な最小ステップ数を求める問題.
横長の車は横にしか,縦長の車は縦にしか動かせない.1度に動かすマス数は任意だが,車を飛び越えたり,他の車と重なるように動けない.
答えは10以下であることが保証されており,テストケースはランダムに生成される.(意地の悪い人工的なテストケースはない)

解法

枝刈り全探索DFSで通った.(想定解法はIDA*らしい)

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int x,y;
char mp[22][22];
int cx[26], cy[26], len[26], dir[26], n;
int dx[2]={1,0}, dy[2]={0,1};
int res;

void print_mp(){
  int i,j;
  rep(i,x){ rep(j,y)putchar(mp[i][j]); puts(""); } puts("");
}

int get_go(int num, int go[]){
  int i,j,k,gos=0;
  int nx, ny;
  for(k=1;;k++){
    nx = cx[num]-dx[dir[num]]*k;
    ny = cy[num]-dy[dir[num]]*k;
    if( nx < 0 || ny < 0) break;
    if( mp[nx][ny]!='.' ) break;
    go[gos++]=-k;
  }
  for(k=1;;k++){
    nx = cx[num]+dx[dir[num]]*(len[num]+k-1);
    ny = cy[num]+dy[dir[num]]*(len[num]+k-1);
    if( nx>=x || ny>=y ) break;
    if( mp[nx][ny]!='.' ) break;
    go[gos++]=k;
  }
  return gos;
}

void get_tonari(int num,int *resA,int *resB){
  int i,j,k;
  *resA=*resB=-1;
  for(k=1;;k++){
    if( cx[num]-dx[dir[num]]*k < 0 || cy[num]-dy[dir[num]]*k < 0) break;
    if( mp[cx[num]-dx[dir[num]]*k][cy[num]-dy[dir[num]]*k]=='.' ) continue;
    *resA = mp[cx[num]-dx[dir[num]]*k][cy[num]-dy[dir[num]]*k]-'a';
    break;
  }
  for(k=1;;k++){
    if( cx[num]+dx[dir[num]]*(len[num]+k-1)>=x || cy[num]+dy[dir[num]]*(len[num]+k-1)>=y ) break;
    if( mp[cx[num]+dx[dir[num]]*(len[num]+k-1)][cy[num]+dy[dir[num]]*(len[num]+k-1)]=='.' ) continue;
    *resB = mp[cx[num]+dx[dir[num]]*(len[num]+k-1)][cy[num]+dy[dir[num]]*(len[num]+k-1)]-'a';
    break;
  }
}

void nul(int sx,int sy,int len,int dir,char c){
  int i;
  rep(i,len) mp[sx+dx[dir]*i][sy+dy[dir]*i]=c;
}


int st[30], st_size;

void solve(int depth, int bef){
  int i,j,k;
  int go[30], reached[30], gos, add, a, b, dame;

  if(cy[0]+len[0]==y){ if(res>depth) res=depth; return; }

  i = cx[0];
  add = 0; dame = 0;
  REP(j,cy[0]+len[0],y) if('a'<=mp[i][j]&&mp[i][j]<='z'){
    add++;
    if( !dame && !get_go(mp[i][j]-'a',go) ) dame = 1;
  }
  add += dame;

  if(depth+add+1 >= res) return;

/*  printf("depth = %d\n",depth);
  print_mp();*/

/*  rep(i,n) reached[i]=0; reached[0]=1;
  st_size=1; st[0]=0;
  while(st_size){
    k = st[--st_size];
    get_tonari(k,&a,&b);
    if(a>=0 && reached[a]==0) reached[a]=1, st[st_size++]=a;
    if(b>=0 && reached[b]==0) reached[b]=1, st[st_size++]=b;
  }*/

  rep(k,n) if(bef!=k) /*if(reached[k])*/{
    gos = get_go(k, go);
    nul(cx[k],cy[k],len[k],dir[k],'.');
    rep(i,gos){
      cx[k] += go[i] * dx[dir[k]];
      cy[k] += go[i] * dy[dir[k]];
      nul(cx[k],cy[k],len[k],dir[k],'a'+k);
      solve(depth+1, k);
      nul(cx[k],cy[k],len[k],dir[k],'.');
      cx[k] -= go[i] * dx[dir[k]];
      cy[k] -= go[i] * dy[dir[k]];
    }
    nul(cx[k],cy[k],len[k],dir[k],'a'+k);
  }

}

int main(){
  int i,j,k,l,m,dum;
  int size;

  scanf("%d",&size);
  while(size--){
    scanf("%d%d%d",&x,&y,&dum);
    rep(i,x) scanf("%s",mp[i]);
    rep(i,26) len[i]=0;

    res = 10;

    rep(i,x) rep(j,y) if('a'<=mp[i][j]&&mp[i][j]<='z'){
      k = mp[i][j]-'a';
      cx[k]=i; cy[k]=j;
      if(i+2 < x && mp[i+2][j]==mp[i][j]){ mp[i][j]=mp[i+1][j]=mp[i+2][j]='.'; dir[k]=0; len[k]=3; continue; }
      if(i+1 < x && mp[i+1][j]==mp[i][j]){ mp[i][j]=mp[i+1][j]='.';            dir[k]=0; len[k]=2; continue; }
      if(j+2 < y && mp[i][j+2]==mp[i][j]){ mp[i][j]=mp[i][j+1]=mp[i][j+2]='.'; dir[k]=1; len[k]=3; continue; }
      if(j+1 < y && mp[i][j+1]==mp[i][j]){ mp[i][j]=mp[i][j+1]='.';            dir[k]=1; len[k]=2; continue; }
    }

    n=0;
    rep(i,26) if(len[i]){
      nul(cx[i],cy[i],len[i],dir[i],'a'+n);
      cx[n]=cx[i]; cy[n]=cy[i]; len[n]=len[i]; dir[n]=dir[i]; n++;
    }

    solve(0,-1);

    printf("%d\n",res);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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