Submission #68772930

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N=5e2+5;
struct node{
	int x,y,s;
};
char a[N][N];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1},dis[N][N][2],n,m,sx,sy,ex,ey;
int bfs(){
	queue<node> q;
	q.push({sx,sy,0});
	int inf=dis[0][0][0];
	dis[sx][sy][0]=0;
	while(!q.empty()){
		int nx=q.front().x,ny=q.front().y,ns=q.front().s;
		q.pop();
		if(a[nx][ny]=='?') ns=1-ns;
		for(int i=0;i<4;i++){
			int xx=nx+dx[i],yy=ny+dy[i];
			if(xx<1||xx>n||yy<1||yy>m||a[xx][yy]=='#'||(ns==0&&a[xx][yy]=='x')||(ns==1&&a[xx][yy]=='o')||dis[xx][yy][ns]!=inf) continue;
			dis[xx][yy][ns]=dis[nx][ny][(a[nx][ny]=='?'?1-ns:ns)]+1;
			q.push({xx,yy,ns});
		}
	}
	return (dis[ex][ey][0]==inf&&dis[ex][ey][1]==inf?-1:min(dis[ex][ey][0],dis[ex][ey][1]));
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='S') sx=i,sy=j;
			else if(a[i][j]=='G') ex=i,ey=j;
		}
	memset(dis,0x3f,sizeof(dis));
	cout<<bfs();		
	return 0;
}

Submission Info

Submission Time
Task D - Toggle Maze
User a_computers_xh
Language C++ 17 (gcc 12.2)
Score 400
Code Size 996 Byte
Status AC
Exec Time 30 ms
Memory 5868 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 2 ms 5512 KiB
00_sample_01.txt AC 2 ms 5396 KiB
00_sample_02.txt AC 2 ms 5428 KiB
01_handmade_00.txt AC 18 ms 5652 KiB
01_handmade_01.txt AC 18 ms 5764 KiB
01_handmade_02.txt AC 18 ms 5552 KiB
01_handmade_03.txt AC 18 ms 5548 KiB
01_handmade_04.txt AC 2 ms 5428 KiB
01_handmade_05.txt AC 2 ms 5388 KiB
01_handmade_06.txt AC 2 ms 5428 KiB
01_handmade_07.txt AC 2 ms 5432 KiB
01_handmade_08.txt AC 2 ms 5444 KiB
01_handmade_09.txt AC 13 ms 5632 KiB
01_handmade_10.txt AC 14 ms 5656 KiB
01_handmade_11.txt AC 20 ms 5728 KiB
01_handmade_12.txt AC 20 ms 5668 KiB
01_handmade_13.txt AC 15 ms 5860 KiB
01_handmade_14.txt AC 16 ms 5652 KiB
02_random_00.txt AC 2 ms 5396 KiB
02_random_01.txt AC 16 ms 5616 KiB
02_random_02.txt AC 3 ms 5420 KiB
02_random_03.txt AC 19 ms 5768 KiB
02_random_04.txt AC 3 ms 5488 KiB
02_random_05.txt AC 21 ms 5644 KiB
02_random_06.txt AC 18 ms 5680 KiB
02_random_07.txt AC 22 ms 5700 KiB
02_random_08.txt AC 4 ms 5680 KiB
02_random_09.txt AC 22 ms 5648 KiB
02_random_10.txt AC 10 ms 5688 KiB
02_random_11.txt AC 22 ms 5648 KiB
02_random_12.txt AC 10 ms 5676 KiB
02_random_13.txt AC 6 ms 5596 KiB
02_random_14.txt AC 19 ms 5636 KiB
02_random_15.txt AC 2 ms 5320 KiB
02_random_16.txt AC 22 ms 5856 KiB
02_random_17.txt AC 2 ms 5676 KiB
02_random_18.txt AC 22 ms 5808 KiB
02_random_19.txt AC 3 ms 5660 KiB
02_random_20.txt AC 22 ms 5664 KiB
02_random_21.txt AC 2 ms 5644 KiB
02_random_22.txt AC 22 ms 5660 KiB
02_random_23.txt AC 3 ms 5388 KiB
02_random_24.txt AC 10 ms 5600 KiB
02_random_25.txt AC 5 ms 5568 KiB
02_random_26.txt AC 9 ms 5392 KiB
02_random_27.txt AC 5 ms 5376 KiB
02_random_28.txt AC 15 ms 5644 KiB
02_random_29.txt AC 7 ms 5700 KiB
02_random_30.txt AC 19 ms 5668 KiB
02_random_31.txt AC 8 ms 5636 KiB
02_random_32.txt AC 12 ms 5648 KiB
02_random_33.txt AC 9 ms 5672 KiB
02_random_34.txt AC 17 ms 5664 KiB
02_random_35.txt AC 6 ms 5556 KiB
02_random_36.txt AC 18 ms 5560 KiB
02_random_37.txt AC 12 ms 5548 KiB
02_random_38.txt AC 30 ms 5724 KiB
02_random_39.txt AC 25 ms 5868 KiB
02_random_40.txt AC 28 ms 5804 KiB
02_random_41.txt AC 2 ms 5428 KiB
02_random_42.txt AC 2 ms 5300 KiB
02_random_43.txt AC 2 ms 5548 KiB
02_random_44.txt AC 2 ms 5788 KiB
02_random_45.txt AC 2 ms 5444 KiB
02_random_46.txt AC 2 ms 5464 KiB
02_random_47.txt AC 2 ms 5684 KiB
02_random_48.txt AC 2 ms 5636 KiB