Submission #32990


Source Code Expand

Copy
#include <iostream>
#include <queue>
#include <algorithm>
#include <cctype>
#include <cstdio>
using namespace std;

#define at(a,x) (a[x/502][x%502])

char mp[502][502];
bool visit[502][502];

int df[4] = {-502, -1, 1, 502};
int s;


bool bfs( double lim ){
	fill( *visit, *visit + sizeof visit, false );

	at( visit, s ) = true;

	queue<int> q;
	q.push( s );
	q.push( -1 );
	
	double k = 0.99;

	while( q.size() > 1 ){
		int x = q.front();
		q.pop();
		
		if( x == -1 ){
			k *= 0.99;
			q.push( -1 );
		}
		else{
			for( int i = 0; i < 4; ++i ){
				int y = x + df[i];
				int c = at( mp, y );
				
				if( at( visit, y ) ) continue;
				
				if( c == 'g' ){
					return true;
				}
				if( isdigit( c ) ){
					if( k * (c - '0') >= lim ){
						at( visit, y ) = true;
						q.push( y );
					}
				}
			}
		}
	}
	
	return false;
}


int main(){
	fill( *mp, *mp + sizeof mp, '#' );

	int n, m;
	cin >> n >> m;

	for( int i = 1; i <= n; ++i ){
		cin >> &mp[i][1];
		mp[i][m + 1] = '#';
	}

	s = find( *mp, *mp + sizeof mp, 's' ) - *mp;
	
	if( !bfs( 0.0 ) ){
		puts("-1");
		return 0;
	}
	
	double left = 0.0;
	double right = 9.0;
	while( right - left > 5e-10 ){
		double mid = 0.5 * (left + right);
		if( bfs( mid ) ){
			left = mid;
		}
		else{
			right = mid;
		}
	}
	printf("%.10f\n", left );
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User climpet
Language C++ (GCC 4.4.7)
Score 100
Code Size 1389 Byte
Status AC
Exec Time 410 ms
Memory 1792 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 64 ms 1708 KB
00_mini_02.txt AC 44 ms 1692 KB
00_mini_03.txt AC 44 ms 1700 KB
00_mini_04.txt AC 44 ms 1704 KB
00_mini_05.txt AC 37 ms 1660 KB
00_sample_01.txt AC 45 ms 1664 KB
00_sample_02.txt AC 43 ms 1676 KB
01_rnd_01.txt AC 273 ms 1668 KB
01_rnd_02.txt AC 91 ms 1672 KB
01_rnd_03.txt AC 47 ms 1672 KB
01_rnd_04.txt AC 69 ms 1672 KB
01_rnd_05.txt AC 46 ms 1676 KB
01_rnd_06.txt AC 43 ms 1664 KB
01_rnd_07.txt AC 48 ms 1652 KB
01_rnd_08.txt AC 116 ms 1672 KB
01_rnd_09.txt AC 148 ms 1676 KB
01_rnd_10.txt AC 189 ms 1676 KB
01_rnd_11.txt AC 118 ms 1672 KB
01_rnd_12.txt AC 91 ms 1664 KB
01_rnd_13.txt AC 54 ms 1676 KB
01_rnd_14.txt AC 240 ms 1668 KB
01_rnd_15.txt AC 131 ms 1672 KB
01_rnd_16.txt AC 46 ms 1668 KB
01_rnd_17.txt AC 42 ms 1668 KB
01_rnd_18.txt AC 34 ms 1672 KB
01_rnd_19.txt AC 37 ms 1668 KB
01_rnd_20.txt AC 34 ms 1664 KB
02_maxrnd_01.txt AC 127 ms 1672 KB
02_maxrnd_02.txt AC 120 ms 1652 KB
02_maxrnd_03.txt AC 141 ms 1680 KB
02_maxrnd_04.txt AC 233 ms 1668 KB
02_maxrnd_05.txt AC 150 ms 1676 KB
02_maxrnd_06.txt AC 364 ms 1676 KB
02_maxrnd_07.txt AC 83 ms 1672 KB
02_maxrnd_08.txt AC 68 ms 1672 KB
02_maxrnd_09.txt AC 410 ms 1676 KB
02_maxrnd_10.txt AC 109 ms 1672 KB
02_maxrnd_11.txt AC 399 ms 1672 KB
02_maxrnd_12.txt AC 220 ms 1668 KB
02_maxrnd_13.txt AC 278 ms 1672 KB
02_maxrnd_14.txt AC 317 ms 1668 KB
02_maxrnd_15.txt AC 91 ms 1668 KB
02_maxrnd_16.txt AC 243 ms 1668 KB
02_maxrnd_17.txt AC 178 ms 1680 KB
02_maxrnd_18.txt AC 45 ms 1664 KB
02_maxrnd_19.txt AC 43 ms 1672 KB
03_hard_01.txt AC 272 ms 1676 KB
03_hard_02.txt AC 269 ms 1672 KB
03_hard_03.txt AC 74 ms 1660 KB
03_hard_04.txt AC 75 ms 1676 KB
03_hard_05.txt AC 274 ms 1648 KB
03_hard_06.txt AC 268 ms 1680 KB
03_hard_07.txt AC 75 ms 1668 KB
03_hard_08.txt AC 76 ms 1660 KB
04_open_01.txt AC 291 ms 1668 KB
04_open_02.txt AC 282 ms 1664 KB
05_minihard_01.txt AC 43 ms 1664 KB
05_minihard_02.txt AC 43 ms 1668 KB
05_minihard_03.txt AC 43 ms 1668 KB
05_minihard_04.txt AC 42 ms 1792 KB
05_minihard_05.txt AC 43 ms 1668 KB
05_minihard_06.txt AC 43 ms 1672 KB
05_minihard_07.txt AC 42 ms 1676 KB
05_minihard_08.txt AC 43 ms 1640 KB