結果

問題 No.1638 Robot Maze
ユーザー snrnsidysnrnsidy
提出日時 2021-08-10 16:12:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 1,633 bytes
コンパイル時間 2,211 ms
コンパイル使用メモリ 208,884 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-24 00:24:01
合計ジャッジ時間 5,028 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 3 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 2 ms
4,348 KB
testcase_12 AC 2 ms
4,348 KB
testcase_13 AC 2 ms
4,348 KB
testcase_14 AC 3 ms
4,348 KB
testcase_15 AC 2 ms
4,348 KB
testcase_16 AC 3 ms
4,348 KB
testcase_17 AC 2 ms
4,348 KB
testcase_18 AC 2 ms
4,348 KB
testcase_19 AC 2 ms
4,348 KB
testcase_20 AC 2 ms
4,348 KB
testcase_21 AC 2 ms
4,348 KB
testcase_22 AC 2 ms
4,348 KB
testcase_23 AC 2 ms
4,348 KB
testcase_24 AC 2 ms
4,348 KB
testcase_25 AC 2 ms
4,348 KB
testcase_26 AC 2 ms
4,348 KB
testcase_27 AC 2 ms
4,348 KB
testcase_28 AC 3 ms
4,348 KB
testcase_29 AC 2 ms
4,348 KB
testcase_30 AC 2 ms
4,348 KB
testcase_31 AC 2 ms
4,348 KB
testcase_32 AC 3 ms
4,348 KB
testcase_33 AC 3 ms
4,348 KB
testcase_34 AC 3 ms
4,348 KB
testcase_35 AC 3 ms
4,348 KB
testcase_36 AC 3 ms
4,348 KB
testcase_37 AC 3 ms
4,348 KB
testcase_38 AC 3 ms
4,348 KB
testcase_39 AC 3 ms
4,348 KB
testcase_40 AC 4 ms
4,348 KB
testcase_41 AC 3 ms
4,348 KB
testcase_42 AC 3 ms
4,348 KB
testcase_43 AC 3 ms
4,348 KB
testcase_44 AC 3 ms
4,348 KB
testcase_45 AC 3 ms
4,348 KB
testcase_46 AC 4 ms
4,348 KB
testcase_47 AC 3 ms
4,348 KB
testcase_48 AC 3 ms
4,348 KB
testcase_49 AC 3 ms
4,348 KB
testcase_50 AC 3 ms
4,348 KB
testcase_51 AC 3 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

long long int dist[105][105];
int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,1,-1};
int cost[4];
int h,w;
long long int k,p;
char board[105][105];
int sy,sx,gy,gx;

int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> h >> w;
	cin >> cost[0] >> cost[1] >> cost[2] >> cost[3] >> k >> p;
	cin >> sy >> sx >> gy >> gx;
	sy-=1;
	sx-=1;
	gy-=1;
	gx-=1;
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			cin >> board[i][j];
		}
	}

	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			dist[i][j] = 1e18;
		}
	}

	dist[sy][sx] = 0;

	priority_queue <pair<long long int,pair<int,int>>,vector<pair<long long int,pair<int,int>>>,greater<pair<long long int,pair<int,int>>>> pque;
	pque.push(make_pair(dist[sy][sx],make_pair(sy,sx)));

	while(!pque.empty())
	{
		int y = pque.top().second.first;
		int x = pque.top().second.second;
		long long int C = pque.top().first;
		pque.pop();
		if(dist[y][x] < C) 
		{
			continue;
		}
		
		for(int k=0;k<4;k++)
		{
			int ny = y + dy[k];
			int nx = x + dx[k];
			if(ny<0 || ny>=h || nx<0 || nx>=w) continue;
			long long int val = cost[k];
			if(board[ny][nx]=='.')
			{
				if(dist[ny][nx] > dist[y][x] + val)
				{
					dist[ny][nx] = dist[y][x] + val;
					pque.push(make_pair(dist[ny][nx],make_pair(ny,nx)));
				}
			}
			else if(board[ny][nx]=='@')
			{
				val += p;
				if(dist[ny][nx] > dist[y][x] + val)
				{
					dist[ny][nx] = dist[y][x] + val;
					pque.push(make_pair(dist[ny][nx],make_pair(ny,nx)));
				}				
			}
		}
	}

	if(dist[gy][gx]<=k)
	{
		cout << "Yes" << '\n';
	}
	else{
		cout << "No" << '\n';
	}
	return 0;
}
0