Submission #1182511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182511		PieArmy	Maze (JOI23_ho_t3)	C++20	100 / 100	276 ms	107468 KiB

Main

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;

int R,C,N;
pair<int,int>G;
vector<vector<int>>table;
vector<pair<int,int>>v;
int X[4]={1,-1,0,0},Y[4]={0,0,1,-1};

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>R>>C>>N;
	cin>>G.fr>>G.sc;
	v.pb(G);
	cin>>G.fr>>G.sc;
	table.resize(R+2,vector<int>(C+2,2));
	for(int i=1;i<=R;i++){
		for(int j=1;j<=C;j++){
			char c;cin>>c;
			table[i][j]=(c=='#');
		}
	}
	table[v.back().fr][v.back().sc]=2;
	for(int ans=0;;ans++){
		vector<pair<int,int>>q;
		swap(q,v);
		while(q.size()){
			pair<int,int>pos=q.back();
			q.pop_back();
			for(int i=0;i<4;i++){
				int &x=table[pos.fr+X[i]][pos.sc+Y[i]];
				if(x==2)continue;
				if(x==1){
					v.pb({pos.fr+X[i],pos.sc+Y[i]});
				}
				else{
					q.pb({pos.fr+X[i],pos.sc+Y[i]});
				}
				x=2;
			}
		}
		/*for(auto x:v){
			cout<<x.fr<<":"<<x.sc<<endl;
		}
		cout<<endl;*/
		if(table[G.fr][G.sc]==2){
			cout<<ans;
			return 0;
		}
		swap(q,v);
		for(int j=1;j<N;j++){
			vector<pair<int,int>>v2;
			for(auto x:q){
				v2.pb(x);
			}
			q.clear();
			for(auto x:v2){
				int &a=table[x.fr+X[2]][x.sc+Y[2]];
				if(a!=2){
					a=2;
					q.pb({x.fr+X[2],x.sc+Y[2]});
				}
				int &b=table[x.fr+X[3]][x.sc+Y[3]];
				if(b!=2){
					b=2;
					q.pb({x.fr+X[3],x.sc+Y[3]});
				}
				v.pb(x);
			}
			v2.clear();
		}
		for(auto x:q){
			v.pb(x);
		}
		swap(q,v);
		for(int j=1;j<N;j++){
			vector<pair<int,int>>v2;
			for(auto x:q){
				v2.pb(x);
			}
			q.clear();
			for(auto x:v2){
				int &a=table[x.fr+X[0]][x.sc+Y[0]];
				if(a!=2){
					a=2;
					q.pb({x.fr+X[0],x.sc+Y[0]});
				}
				int &b=table[x.fr+X[1]][x.sc+Y[1]];
				if(b!=2){
					b=2;
					q.pb({x.fr+X[1],x.sc+Y[1]});
				}
				v.pb(x);
			}
			v2.clear();
		}
		for(auto x:q){
			v.pb(x);
		}
	}
	cout<<"Merhaba ben PieArmy ve ben bu sorudan ac alacagim. Evet dogru duydun JOI 2023 Final Round Problem 3'u cozecegim ve bu sorudan tam olarak 100 puan alacagim. Neden guluyorsun? Bu gercek olacak. Inanmıyorsan izle de gor bakayim >:(";
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 16 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 19 / 19
• Subtask 7: 8 / 8
• Subtask 8: 6 / 6