Submission #580122


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
#define FOR(i,a,b) for (int i=(a); i<(b); i++)
typedef pair<int,int> PII;
typedef pair<int,pair<int,int> > PIII;
typedef pair<ll,ll> PLL;

const int INF = (1<<28);

int N,M;
int c[512][512];
PII s;
int dist[512][512]; //最小コスト

int dy[] = {-1,0,1,0};
int dx[] = {0,1,0,-1};

bool f(int ny, int nx){
    return (0<=ny && ny < N && 0<=nx && nx < M);
}

// 明るさl以上の経路が存在するか否か
bool check(double l){
    queue<PIII> q; //時間 y x
    for(int y=0;y<512;y++) for(int x=0;x<512;x++) { dist[y][x]=INF; }

    q.push(PIII(0, PII(s.first, s.second)));

    // BFS
    while(!q.empty()){
        PIII p = q.front(); q.pop();


        if(dist[p.second.first][p.second.second] <= p.first) { continue; }
        dist[p.second.first][p.second.second] = p.first;

        //cout<<p.second.first<<":"<<p.second.second<<endl;

        for(int k=0;k<4;k++){
            int ny = p.second.first  + dy[k];
            int nx = p.second.second + dx[k];
            int nt = p.first+1;


            if(f(ny,nx) && '0'<=c[ny][nx] && c[ny][nx]<='9' && (c[ny][nx]-'0')*pow(0.99,nt)>=l ){
                q.push(PIII(nt, PII(ny,nx)));
            }else if(f(ny,nx) && c[ny][nx]=='g'){
                return true;
            }
        }
    }

    return false;
}

int main(){
    cin>>N>>M;
    for(int y=0;y<N;y++){
        string str;
        cin>>str;
        for(int x=0;x<M;x++){
            c[y][x] = str[x];
            if(c[y][x]=='s'){
                s.first = y;
                s.second = x;
            }
        }
    }

    if(!check(-1.0)){
        cout<<"-1"<<endl;
        return 0;
    }

    double l=0.0, r=10.0;
    while(r-l >= 1e-10){
        double m = (r+l)/2;
        if(check(m)){
            l=m;
        }else{
            r=m;
        }
    }

    printf("%.9f\n",l);
    return 0;
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User bobuhiro11
Language C++11 (GCC 4.8.1)
Score 100
Code Size 2030 Byte
Status AC
Exec Time 4787 ms
Memory 3188 KB

Judge Result

Set Name all
Score / Max Score 100 / 100
Status
AC × 64
Set Name Test Cases
all 00_mini_01.txt, 00_mini_02.txt, 00_mini_03.txt, 00_mini_04.txt, 00_mini_05.txt, 00_sample_01.txt, 00_sample_02.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 02_maxrnd_01.txt, 02_maxrnd_02.txt, 02_maxrnd_03.txt, 02_maxrnd_04.txt, 02_maxrnd_05.txt, 02_maxrnd_06.txt, 02_maxrnd_07.txt, 02_maxrnd_08.txt, 02_maxrnd_09.txt, 02_maxrnd_10.txt, 02_maxrnd_11.txt, 02_maxrnd_12.txt, 02_maxrnd_13.txt, 02_maxrnd_14.txt, 02_maxrnd_15.txt, 02_maxrnd_16.txt, 02_maxrnd_17.txt, 02_maxrnd_18.txt, 02_maxrnd_19.txt, 03_hard_01.txt, 03_hard_02.txt, 03_hard_03.txt, 03_hard_04.txt, 03_hard_05.txt, 03_hard_06.txt, 03_hard_07.txt, 03_hard_08.txt, 04_open_01.txt, 04_open_02.txt, 05_minihard_01.txt, 05_minihard_02.txt, 05_minihard_03.txt, 05_minihard_04.txt, 05_minihard_05.txt, 05_minihard_06.txt, 05_minihard_07.txt, 05_minihard_08.txt
Case Name Status Exec Time Memory
00_mini_01.txt AC 50 ms 1844 KB
00_mini_02.txt AC 32 ms 1900 KB
00_mini_03.txt AC 33 ms 1904 KB
00_mini_04.txt AC 33 ms 1900 KB
00_mini_05.txt AC 26 ms 1952 KB
00_sample_01.txt AC 33 ms 1952 KB
00_sample_02.txt AC 32 ms 1892 KB
01_rnd_01.txt AC 3866 ms 2924 KB
01_rnd_02.txt AC 488 ms 2792 KB
01_rnd_03.txt AC 70 ms 2156 KB
01_rnd_04.txt AC 279 ms 2412 KB
01_rnd_05.txt AC 64 ms 2072 KB
01_rnd_06.txt AC 40 ms 2080 KB
01_rnd_07.txt AC 67 ms 2924 KB
01_rnd_08.txt AC 598 ms 2924 KB
01_rnd_09.txt AC 882 ms 2912 KB
01_rnd_10.txt AC 1177 ms 2932 KB
01_rnd_11.txt AC 608 ms 2540 KB
01_rnd_12.txt AC 374 ms 2284 KB
01_rnd_13.txt AC 113 ms 2076 KB
01_rnd_14.txt AC 1415 ms 2664 KB
01_rnd_15.txt AC 628 ms 2416 KB
01_rnd_16.txt AC 39 ms 2408 KB
01_rnd_17.txt AC 51 ms 2540 KB
01_rnd_18.txt AC 28 ms 2124 KB
01_rnd_19.txt AC 31 ms 2720 KB
01_rnd_20.txt AC 31 ms 2916 KB
02_maxrnd_01.txt AC 1012 ms 3048 KB
02_maxrnd_02.txt AC 659 ms 3048 KB
02_maxrnd_03.txt AC 1098 ms 3052 KB
02_maxrnd_04.txt AC 1924 ms 3040 KB
02_maxrnd_05.txt AC 1038 ms 3052 KB
02_maxrnd_06.txt AC 3705 ms 3052 KB
02_maxrnd_07.txt AC 304 ms 3044 KB
02_maxrnd_08.txt AC 148 ms 3044 KB
02_maxrnd_09.txt AC 3289 ms 3048 KB
02_maxrnd_10.txt AC 473 ms 3052 KB
02_maxrnd_11.txt AC 2809 ms 3056 KB
02_maxrnd_12.txt AC 1265 ms 3044 KB
02_maxrnd_13.txt AC 1689 ms 3048 KB
02_maxrnd_14.txt AC 1904 ms 3044 KB
02_maxrnd_15.txt AC 310 ms 3044 KB
02_maxrnd_16.txt AC 1353 ms 3048 KB
02_maxrnd_17.txt AC 905 ms 3056 KB
02_maxrnd_18.txt AC 46 ms 3040 KB
02_maxrnd_19.txt AC 45 ms 3052 KB
03_hard_01.txt AC 4267 ms 3044 KB
03_hard_02.txt AC 4439 ms 3048 KB
03_hard_03.txt AC 117 ms 3180 KB
03_hard_04.txt AC 138 ms 3176 KB
03_hard_05.txt AC 4315 ms 3060 KB
03_hard_06.txt AC 4402 ms 2980 KB
03_hard_07.txt AC 116 ms 3184 KB
03_hard_08.txt AC 136 ms 3188 KB
04_open_01.txt AC 4787 ms 3052 KB
04_open_02.txt AC 4544 ms 3048 KB
05_minihard_01.txt AC 46 ms 2028 KB
05_minihard_02.txt AC 46 ms 2024 KB
05_minihard_03.txt AC 40 ms 2028 KB
05_minihard_04.txt AC 42 ms 2040 KB
05_minihard_05.txt AC 44 ms 2080 KB
05_minihard_06.txt AC 49 ms 2168 KB
05_minihard_07.txt AC 39 ms 2072 KB
05_minihard_08.txt AC 40 ms 2080 KB