Submission #68757295

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define mt make_tuple
#define g(aaa) get<aaa>(q.front())
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
int x,y;
char m[505][505];
bool flag[505][505][2];
queue<tuple<int,int,int,int> >q;
int qx,qy,mx,my;
int main(){
	x=read();
	y=read();
	for(int i=1;i<=x;i++){
		for(int j=1;j<=y;j++){
			cin>>m[i][j];
			if(m[i][j]=='S'){
				qx=i;
				qy=j;
			}
			if(m[i][j]=='G'){
				mx=i;
				my=j;
			}
		} 
	}
	q.push(mt(qx,qy,0,0));
	while(!q.empty()){
		int mqx=g(0);
		int mqy=g(1);
		int mqs=g(2);
		int mqf=g(3);
		q.pop();
		if(mqx<=0||mqx>x||mqy<=0||mqy>y) continue;
		if(m[mqx][mqy]=='#') continue;
		if(m[mqx][mqy]=='o'&&mqf==1) continue;
		if(m[mqx][mqy]=='x'&&mqf==0) continue;
		if(flag[mqx][mqy][mqf]==true) continue;
		flag[mqx][mqy][mqf]=true;
		if(mqx==mx&&mqy==my){
			write(mqs);
			exit(0);
		}
		if(m[mqx][mqy]=='?') mqf^=1;
		q.push(mt(mqx+1,mqy,mqs+1,mqf));
		q.push(mt(mqx,mqy+1,mqs+1,mqf));
		q.push(mt(mqx-1,mqy,mqs+1,mqf));
		q.push(mt(mqx,mqy-1,mqs+1,mqf));
	}
	write(-1);
	return 0;
}

Submission Info

Submission Time
Task D - Toggle Maze
User Fireflies
Language C++ 20 (gcc 12.2)
Score 400
Code Size 1371 Byte
Status AC
Exec Time 27 ms
Memory 4452 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 67
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_handmade_00.txt, 01_handmade_01.txt, 01_handmade_02.txt, 01_handmade_03.txt, 01_handmade_04.txt, 01_handmade_05.txt, 01_handmade_06.txt, 01_handmade_07.txt, 01_handmade_08.txt, 01_handmade_09.txt, 01_handmade_10.txt, 01_handmade_11.txt, 01_handmade_12.txt, 01_handmade_13.txt, 01_handmade_14.txt, 02_random_00.txt, 02_random_01.txt, 02_random_02.txt, 02_random_03.txt, 02_random_04.txt, 02_random_05.txt, 02_random_06.txt, 02_random_07.txt, 02_random_08.txt, 02_random_09.txt, 02_random_10.txt, 02_random_11.txt, 02_random_12.txt, 02_random_13.txt, 02_random_14.txt, 02_random_15.txt, 02_random_16.txt, 02_random_17.txt, 02_random_18.txt, 02_random_19.txt, 02_random_20.txt, 02_random_21.txt, 02_random_22.txt, 02_random_23.txt, 02_random_24.txt, 02_random_25.txt, 02_random_26.txt, 02_random_27.txt, 02_random_28.txt, 02_random_29.txt, 02_random_30.txt, 02_random_31.txt, 02_random_32.txt, 02_random_33.txt, 02_random_34.txt, 02_random_35.txt, 02_random_36.txt, 02_random_37.txt, 02_random_38.txt, 02_random_39.txt, 02_random_40.txt, 02_random_41.txt, 02_random_42.txt, 02_random_43.txt, 02_random_44.txt, 02_random_45.txt, 02_random_46.txt, 02_random_47.txt, 02_random_48.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 3500 KiB
00_sample_01.txt AC 1 ms 3556 KiB
00_sample_02.txt AC 1 ms 3428 KiB
01_handmade_00.txt AC 18 ms 4160 KiB
01_handmade_01.txt AC 20 ms 4200 KiB
01_handmade_02.txt AC 19 ms 4228 KiB
01_handmade_03.txt AC 17 ms 4240 KiB
01_handmade_04.txt AC 1 ms 3624 KiB
01_handmade_05.txt AC 1 ms 3500 KiB
01_handmade_06.txt AC 1 ms 3432 KiB
01_handmade_07.txt AC 1 ms 3556 KiB
01_handmade_08.txt AC 1 ms 3632 KiB
01_handmade_09.txt AC 15 ms 4416 KiB
01_handmade_10.txt AC 14 ms 4288 KiB
01_handmade_11.txt AC 10 ms 3956 KiB
01_handmade_12.txt AC 20 ms 4348 KiB
01_handmade_13.txt AC 12 ms 4204 KiB
01_handmade_14.txt AC 14 ms 4452 KiB
02_random_00.txt AC 1 ms 3568 KiB
02_random_01.txt AC 11 ms 3956 KiB
02_random_02.txt AC 2 ms 3540 KiB
02_random_03.txt AC 17 ms 4180 KiB
02_random_04.txt AC 2 ms 3544 KiB
02_random_05.txt AC 20 ms 4428 KiB
02_random_06.txt AC 12 ms 4124 KiB
02_random_07.txt AC 10 ms 3880 KiB
02_random_08.txt AC 3 ms 3940 KiB
02_random_09.txt AC 17 ms 4324 KiB
02_random_10.txt AC 9 ms 3796 KiB
02_random_11.txt AC 23 ms 4336 KiB
02_random_12.txt AC 9 ms 3748 KiB
02_random_13.txt AC 4 ms 3908 KiB
02_random_14.txt AC 19 ms 4172 KiB
02_random_15.txt AC 2 ms 3556 KiB
02_random_16.txt AC 22 ms 4268 KiB
02_random_17.txt AC 2 ms 4080 KiB
02_random_18.txt AC 20 ms 4384 KiB
02_random_19.txt AC 3 ms 4268 KiB
02_random_20.txt AC 15 ms 4212 KiB
02_random_21.txt AC 1 ms 3832 KiB
02_random_22.txt AC 17 ms 4172 KiB
02_random_23.txt AC 2 ms 3580 KiB
02_random_24.txt AC 7 ms 3892 KiB
02_random_25.txt AC 4 ms 3832 KiB
02_random_26.txt AC 6 ms 3944 KiB
02_random_27.txt AC 3 ms 3772 KiB
02_random_28.txt AC 12 ms 4080 KiB
02_random_29.txt AC 6 ms 4180 KiB
02_random_30.txt AC 17 ms 4248 KiB
02_random_31.txt AC 8 ms 3896 KiB
02_random_32.txt AC 11 ms 4384 KiB
02_random_33.txt AC 8 ms 4092 KiB
02_random_34.txt AC 12 ms 3964 KiB
02_random_35.txt AC 3 ms 3620 KiB
02_random_36.txt AC 9 ms 3852 KiB
02_random_37.txt AC 10 ms 3752 KiB
02_random_38.txt AC 10 ms 4068 KiB
02_random_39.txt AC 18 ms 4320 KiB
02_random_40.txt AC 27 ms 4300 KiB
02_random_41.txt AC 1 ms 3504 KiB
02_random_42.txt AC 1 ms 3564 KiB
02_random_43.txt AC 2 ms 4164 KiB
02_random_44.txt AC 2 ms 4284 KiB
02_random_45.txt AC 1 ms 3464 KiB
02_random_46.txt AC 1 ms 3432 KiB
02_random_47.txt AC 1 ms 4036 KiB
02_random_48.txt AC 1 ms 3872 KiB