Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

ARC 005 C - 器物損壊!高橋君 (Search and destroy) (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #005
問題文

問題概要

H*W (500*500以下) のグリッドが与えられる.
各セルは,通れるセルか,塀があるセルかのどちらか.
上下左右に移動でき,2個まで塀を壊すことができる.
スタートからゴールまで移動できるかどうかを判定する問題.

解法

何回塀を壊したかでノードを多重化してBFS,DFSなどする.

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

int st[2000000], st_size;
char reach[2000000];

int main(){
  int i,j,k,l,m,n;
  int x, y, xy, ok;
  int ft, ed;
  char mp[510][510];
  int dx[4] = {-1,1,0,0}, dy[4]={0,0,1,-1};
  int br, sx, sy, nx, ny, nbr, go;

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

  rep(i,x) rep(j,y){
    if(mp[i][j]=='s'){ ft=i*y+j; mp[i][j] = '.'; }
    if(mp[i][j]=='g'){ ed=i*y+j; mp[i][j] = '.'; }
  }

  ok = 0;
  st_size = 0;
  st[st_size++] = ft;

  rep(i,3*xy) reach[i] = 0;
  reach[ft] = 1;

  while(st_size){
    k = st[--st_size];
    br = k/xy; k %= xy;
    sx = k/y; sy = k%y;

    rep(k,4){
      nx = sx + dx[k];
      ny = sy + dy[k];
      nbr = br;
      if(nx < 0 || ny < 0 || nx >= x || ny >= y) continue;
      if(mp[nx][ny]=='#') nbr++;
      if(nbr >= 3) continue;

      go = nbr * xy + nx * y + ny;
      if(reach[go]) continue;
      reach[go] = 1; st[st_size++] = go;
      if(nx*y+ny==ed) ok=1;
    }
    if(ok) break;
  }

  if(ok) puts("YES"); else puts("NO");

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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