Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

ARC 003 C - 暗闇帰り道 (この記事を編集する[管理者用])

Source

AtCoder Regular Contest #003
問題文

問題概要

N*M (500*500以下) のグリッドが与えられる.
また,各セルの明るさの初期値 (1以上9以下) が与えられる.
時間t後の各セルの明るさは 明るさの初期値 * 0.99^t となる.
上下左右に1マス移動すると,移動後に時間が1進む.
始点から終点まで移動するのに,通るセルの明るさの最小値を最大化したい.
最大値を求める問題.

解法

答えに対して2分探索する.
答えを決めると,各セルについて,どの時間までなら通ることができるか決まるので,BFSでゴールに辿り着けるかどうか判定できる.

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)

char mp[510][510];
int dp[510][510];
int q[1000000], q_st, q_size;

int main(){
  int i,j,k,l,m,n;
  int x, y;
  double A, B, C;
  double pw[100000];
  int ok[10];
  int ni, nj, si, sj;
  int dx[4] = {1,-1,0,0};
  int dy[4] = {0,0,1,-1};

  int SX, SY, EX, EY;


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

  rep(i,x) rep(j,y){
    if(mp[i][j]=='s') SX=i, SY=j;
    if(mp[i][j]=='g') EX=i, EY=j;
  }

  A = 0; B = 9;

  pw[0] = 1;
  REP(i,1,100000) pw[i] = pw[i-1] * 0.99;

    rep(i,x) rep(j,y) dp[i][j] = -1;
    dp[SX][SY] = 0;
    q_st = q_size = 0;
    q[q_st+q_size++] = SX*y+SY;
    while(q_size){
      k = q[q_st++]; q_size--;
      si = k/y; sj = k%y;
      rep(k,4){
        ni = si + dx[k];
        nj = sj + dy[k];
        if(ni < 0 || nj < 0 || ni >= x || nj >= y || mp[ni][nj]=='#') continue;
        if(dp[ni][nj] >= 0) continue;
/*        if('0'<=mp[ni][nj] && mp[ni][nj] <= '9' && dp[si][sj] + 1 > ok[mp[ni][nj]-'0']) continue;*/
        dp[ni][nj] = dp[si][sj] + 1;
        q[q_st+q_size++] = ni*y+nj;
      }
      if(dp[EX][EY] >= 0) break;
    }
  if(dp[EX][EY] == -1){ puts("-1"); return 0; }


  while(B-A > 5e-10){
    C = (A+B)/2;
    rep(i,10){
      rep(j,100000) if(i * pw[j] < C){
        ok[i] = j-1; break;
      }
    }

    rep(i,x) rep(j,y) dp[i][j] = -1;
    dp[SX][SY] = 0;
    q_st = q_size = 0;
    q[q_st+q_size++] = SX*y+SY;
    while(q_size){
      k = q[q_st++]; q_size--;
      si = k/y; sj = k%y;
      rep(k,4){
        ni = si + dx[k];
        nj = sj + dy[k];
        if(ni < 0 || nj < 0 || ni >= x || nj >= y || mp[ni][nj]=='#') continue;
        if(dp[ni][nj] >= 0) continue;
        if('0'<=mp[ni][nj] && mp[ni][nj] <= '9' && dp[si][sj] + 1 > ok[mp[ni][nj]-'0']) continue;
        dp[ni][nj] = dp[si][sj] + 1;
        q[q_st+q_size++] = ni*y+nj;
      }
      if(dp[EX][EY] >= 0) break;
    }
    if(dp[EX][EY] >= 0) A=C; else B=C;
  }

  printf("%.10f\n",(A+B)/2);

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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