Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Facebook Hacker Cup 2011 Round 1A [無効試合] 1問目 - After the Dance Battle (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2011 Round 1A [無効試合] 1問目
Facebook Hacker Cup 2011 Round 1A [無効試合]の参加記録

問題概要

100*100以下のグリッドが与えられる.
スタート地点,ゴール地点が1箇所ずつ与えられるので,スタートからゴールまでのステップ数の最小値を求める問題.
グリッドは壁(入れない)か空白(0)か色がぬられている(1--9).
1ステップでできる行動は上下左右に移動するか,同じ色の他のセルにワープすることができる.

解法

BFSするだけ.

C言語のスパゲッティなコード (not verified)
#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 q[11111], q_st, q_size;
int col[10][11111], col_size[10];
int dist[11111];
char mp[111][111];

int main(){
  int i,j,k,l,m,n;
  int x,y,xy;
  int st, ed;
  int size;
  int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
  int sx, sy, sxy, nx, ny, nxy;

  scanf("%d",&size);
  while(size--){
    scanf("%d%d",&x,&y);
    rep(i,x) scanf("%s",mp[i]);
    xy = x*y;

    rep(i,10) col_size[i]=0;
    rep(i,x) rep(j,y){
      if(mp[i][j]=='S') mp[i][j]='0', st=i*y+j;
      if(mp[i][j]=='E') mp[i][j]='0', ed=i*y+j;
      if('1'<=mp[i][j] && mp[i][j]<='9'){
        k=mp[i][j]-'0';
        col[k][col_size[k]++]=i*y+j;
      }
    }

    rep(i,xy) dist[i]=-1;
    dist[st] = 0;
    q[0]=st; q_st=0; q_size=1;
    while(q_size){
      sxy = q[q_st++]; q_size--;
      sx = sxy/y; sy = sxy%y;
      rep(k,4){
        nx = sx + dx[k]; ny = sy + dy[k]; nxy = nx*y + ny;
        if(nx<0||ny<0||nx>=x||ny>=y||mp[nx][ny]=='W'||dist[nxy]!=-1) continue;
        dist[nxy] = dist[sxy]+1;
        q[q_st+q_size++] = nxy;
      }
      if('1'<=mp[sx][sy]&&mp[sx][sy]<='9'){
        m = mp[sx][sy]-'0';
        rep(k,col_size[m]){
          nxy = col[m][k];
          if(dist[nxy]==-1) dist[nxy]=dist[sxy]+1, q[q_st+q_size++]=nxy;
        }
      }
    }

    printf("%d\n",dist[ed]);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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