Submission #74884088

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int H, W;
int si, sj, gi, gj;
int di[4] = {1, 0, -1, 0};
int dj[4] = {0, 1, 0, -1};
string l = "DRUL";
vector<char> ans;
bool flag = false;
vector<vector<vector<bool>>> visit(1000, vector<vector<bool>>(1000, vector<bool>(4, false)));

void dfs(vector<string>& S, int i, int j, int dir){
	if (flag) return;
	if (dir!=-1){
		if (visit[i][j][dir]) return;
		visit[i][j][dir] = true;
	}
	if (gi==i&&gj==j){
		if (!flag){
			flag = true;
			cout<<"Yes"<<endl;
			for (char c : ans) cout<<c;
			cout<<endl;
		}
	}
	if (S[i][j]=='o'){
		int ni = i+di[dir], nj = j+dj[dir];
		if (ni<0||ni>=H||nj<0||nj>=W) return;
		if (S[ni][nj]=='#') return;
		ans.push_back(l[dir]);
		dfs(S, ni, nj, dir);
		ans.pop_back();
		return;
	}
	for (int k=0; k<4; k++){
		int ni=i+di[k], nj=j+dj[k];
		if (ni<0||ni>=H||nj<0||nj>=W) continue;
		if (S[ni][nj]=='#') continue;
		if (S[i][j]=='x'&&dir==k) continue;
		ans.push_back(l[k]);
		dfs(S, ni, nj, k);
		ans.pop_back();
	}
};

int main(){
	cin>>H>>W;
	vector<string> S(H);
	for (int i=0; i<H; i++) cin>>S[i];
	for (int i=0; i<H; i++){
		for (int j=0; j<W; j++){
			if (S[i][j]=='S'){
				si = i;
				sj = j;
			}
			if (S[i][j]=='G'){
				gi = i;
				gj = j;
			}
		}
	}
	dfs(S, si, sj, -1);
	if (!flag) cout<<"No"<<endl;
}

Submission Info

Submission Time
Task D - Go Straight
User circled_9
Language C++23 (GCC 15.2.0)
Score 425
Code Size 1392 Byte
Status AC
Exec Time 510 ms
Memory 704968 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 425 / 425
Status
AC × 3
AC × 46
Set Name Test Cases
Sample example_00.txt, example_01.txt, example_02.txt
All example_00.txt, example_01.txt, example_02.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt
Case Name Status Exec Time Memory
example_00.txt AC 57 ms 73696 KiB
example_01.txt AC 56 ms 73840 KiB
example_02.txt AC 57 ms 73640 KiB
hand_00.txt AC 64 ms 76168 KiB
hand_01.txt AC 64 ms 76028 KiB
hand_02.txt AC 495 ms 704968 KiB
hand_03.txt AC 510 ms 703680 KiB
hand_04.txt AC 58 ms 73840 KiB
hand_05.txt AC 456 ms 702724 KiB
hand_06.txt AC 250 ms 388712 KiB
hand_07.txt AC 455 ms 704028 KiB
hand_08.txt AC 72 ms 75808 KiB
hand_09.txt AC 57 ms 73564 KiB
random_00.txt AC 69 ms 74940 KiB
random_01.txt AC 228 ms 171572 KiB
random_02.txt AC 108 ms 110440 KiB
random_03.txt AC 69 ms 75680 KiB
random_04.txt AC 127 ms 122608 KiB
random_05.txt AC 151 ms 93048 KiB
random_06.txt AC 71 ms 75964 KiB
random_07.txt AC 70 ms 75632 KiB
random_08.txt AC 108 ms 87828 KiB
random_09.txt AC 123 ms 97440 KiB
random_10.txt AC 124 ms 97784 KiB
random_11.txt AC 140 ms 91296 KiB
random_12.txt AC 112 ms 93612 KiB
random_13.txt AC 69 ms 74864 KiB
random_14.txt AC 109 ms 91596 KiB
random_15.txt AC 63 ms 74912 KiB
random_16.txt AC 69 ms 74828 KiB
random_17.txt AC 62 ms 74880 KiB
random_18.txt AC 62 ms 75036 KiB
random_19.txt AC 65 ms 76308 KiB
random_20.txt AC 69 ms 74876 KiB
random_21.txt AC 65 ms 78252 KiB
random_22.txt AC 63 ms 75816 KiB
random_23.txt AC 64 ms 76436 KiB
random_24.txt AC 76 ms 81800 KiB
random_25.txt AC 71 ms 76492 KiB
random_26.txt AC 63 ms 75392 KiB
random_27.txt AC 168 ms 214356 KiB
random_28.txt AC 70 ms 75816 KiB
random_29.txt AC 74 ms 79624 KiB
random_30.txt AC 94 ms 100360 KiB
random_31.txt AC 79 ms 94412 KiB
random_32.txt AC 74 ms 78356 KiB