結果

問題 No.1638 Robot Maze
コンテスト
ユーザー snrnsidy
提出日時 2021-08-10 16:12:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 1,633 bytes
コンパイル時間 2,008 ms
コンパイル使用メモリ 200,412 KB
最終ジャッジ日時 2025-01-23 17:23:42
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

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