#311849 (C++17) No.323 yuki国

• 問題: No.323 yuki国
• ユーザー: ciel
• 提出日時: 2019-01-21 23:53:24
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2,986 ms / 5,000 ms
• コード長: 935 bytes
• コンパイル時間: 1,345 ms
• コンパイル使用メモリ: 98,348 KB
• 実行使用メモリ: 89,344 KB
• 最終ジャッジ日時: 2024-09-15 13:29:10
• 合計ジャッジ時間: 35,714 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2,149 ms; 85,760 KB
testcase_09	AC	2,239 ms; 85,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	2,107 ms; 85,376 KB
testcase_14	AC	2,125 ms; 89,344 KB
testcase_15	AC	2,314 ms; 72,320 KB
testcase_16	AC	2,284 ms; 85,760 KB
testcase_17	AC	2,746 ms; 81,536 KB
testcase_18	AC	14 ms; 5,376 KB
testcase_19	AC	1,779 ms; 54,528 KB
testcase_20	AC	36 ms; 5,504 KB
testcase_21	AC	2,986 ms; 82,560 KB
testcase_22	AC	605 ms; 25,088 KB
testcase_23	AC	2,780 ms; 78,464 KB
testcase_24	AC	143 ms; 10,240 KB
testcase_25	AC	2,820 ms; 80,512 KB
testcase_26	AC	136 ms; 10,240 KB
testcase_27	AC	181 ms; 11,904 KB
testcase_28	AC	2,804 ms; 85,760 KB
testcase_29	AC	2,660 ms; 86,144 KB
testcase_30	AC	2 ms; 5,376 KB
testcase_31	AC	2 ms; 5,376 KB
testcase_32	AC	2 ms; 5,376 KB
testcase_33	AC	2 ms; 5,376 KB
testcase_34	AC	2 ms; 5,376 KB
testcase_35	AC	2 ms; 5,376 KB
testcase_36	AC	2 ms; 5,376 KB
testcase_37	AC	2 ms; 5,376 KB

ソースコード

#include <iostream>
#include <string>
#include <queue>
#include <map>
using namespace std;

typedef struct{
	int x;
	int y;
}dir;
const dir D[]={
	{0,-1},{0,1},{-1,0},{1,0}
};

int main(){
	int H,W,A,Sx,Sy,B,Gx,Gy;
	cin>>H>>W>>A>>Sy>>Sx>>B>>Gy>>Gx;
	vector<string>v(H);
	for(int i=0;i<H;i++)cin>>v[i];
	queue<tuple<int,int,int>>q;
	q.emplace(Sx,Sy,A);
	map<tuple<int,int,int>,int>depth={ {make_tuple(Sx,Sy,A),0} };
	for(;!q.empty();){
		auto cur=q.front();q.pop();
		int cx=get<0>(cur),cy=get<1>(cur),cw=get<2>(cur);
		for(auto &d:D){
			if(0<=cx+d.x&&cx+d.x<W && 0<=cy+d.y&&cy+d.y<H){
				int w=cw+(v[cy+d.y][cx+d.x]=='*' ? 1 : -1);
				if(1<=w && w<=max(A,B)+H+W){
					if(cx+d.x==Gx && cy+d.y==Gy && w==B){
						cout<<"Yes"<<endl;
						return 0;
					}
					auto nxt=make_tuple(cx+d.x,cy+d.y,w);
					if(depth.find(nxt)==depth.end()){
						q.push(nxt);
						depth[nxt]=depth[cur]+1;
					}
				}
			}
		}
	}
	cout<<"No"<<endl;
}