保存されている過去のバージョンの一覧

2014年05月24日04時11分58秒

AtCoder Beginner Contest #007 C問題 - 幅優先探索

Source

AtCoder Beginner Contest #007
問題文

問題概要

$R$ 行 $C$ 列の盤面が与えられる．
各マスは，障害物があるか，空か，で，$1$ ステップで上下左右の空のセルに移動できる．
スタート地点とゴール地点（両方とも空のセルで，移動可能なことは保証されている）が与えられるので，
スタート地点からゴール地点まで最短で何ステップで移動できるかを求める問題．
このような問題は，幅優先探索で解けること，幅優先探索の説明が問題に書かれている．

解法

問題文に書かれている通りにBFSすれば良い．

C++によるスパゲッティなソースコード

#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<iostream>
#include<cmath>
using namespace std;

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

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(char x[], int len){int i,k;if(len==0)return;for(;;){mygc(k);if(!(k==' '||k=='\n'||k=='\t'||k=='\r')){x[0]=k;break;}}REP(i,1,len)mygc(x[i]);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

int main(){
  int R, C, sr, sc, gr, gc, S, G;
  char c[3000];

  int i, j, k, RC;
  int q[3000], q_st, q_size;
  int dist[3000];

  reader(&R);
  reader(&C);
  reader(&sr);
  reader(&sc);
  reader(&gr);
  reader(&gc);
  rep(i,R) reader(c+i*C, C);

  RC = R*C;
  S = (sr-1) * C + (sc - 1);
  G = (gr-1) * C + (gc - 1);

  int d[4] = {-1, 1, -C, C};

  rep(i,RC) dist[i] = -1;
  dist[S] = 0;
  q[0] = S; q_st = 0; q_size = 1;

  while(q_size){
    i = q[q_st++]; q_size--;
    rep(k,4){
      j = i + d[k];
      if(c[j]=='#' || dist[j] >= 0) continue;
      dist[j] = dist[i] + 1;
      q[q_st+q_size++] = j;
    }
  }

  writer(dist[G], '\n');

  return 0;
}

Current time: 2024年04月20日01時20分25秒
Last modified: 2014年05月24日04時11分58秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Beginner_Contest ABC007 ABC_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン：