Submission #1046864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046864		1L1YA	Maze (JOI23_ho_t3)	C++17	43 / 100	153 ms	348900 KiB

Main

//1L1YA
 
#include<bits/stdc++.h>
using namespace std;
 
//#pragma GCC optimize ("O3,unrool-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
typedef long long       ll;
typedef pair<ll,ll>     pll;
typedef pair<int,int>   pii;
 
#define Pb              push_back
#define F               first
#define S               second
#define endl            '\n'
#define sep             ' '
#define all(x)          x.begin(),x.end()
#define al(x,n)         x+1,x+n+1
#define SZ(x)           ((int)x.size())
#define lc              (id<<1)
#define rc              (lc|1)
#define mid             (l+r>>1)
#define dokme(x)        cout << x << endl, exit(0)
#define sik(x)          cout << x << endl;continue;
#define FastIO          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FileIO          freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll oo=1e18;
const int mod=1e9+7;
const int inf=1e9+111;
const int N=6e6+11;
const int lg=23;
 
int n,m,k,xs,ys,xt,yt,x[4]={0,0,-1,1},y[4]={-1,1,0,0};
vector<int> d[N];
string s[N];
 
void bfs(){
	queue<pii> Q;
	queue<pair<pii,pii>> QQ;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			d[i][j]=inf;
	d[xs][ys]=0;
	QQ.push({{xs,ys},{0,0}});
	while(!QQ.empty()){
		int p=QQ.front().F.F,q=QQ.front().F.S;QQ.pop();
		Q.push({p,q});
		for(int i=0;i<4;i++)
			if(p+x[i] && p+x[i]<=n && q+y[i] && q+y[i]<=m && d[p+x[i]][q+y[i]] && s[p+x[i]][q+y[i]]=='.'){
				d[p+x[i]][q+y[i]]=0;
				QQ.push({{p+x[i],q+y[i]},{0,0}});
			}
	}
	while(!Q.empty() || !QQ.empty()){
		while(!Q.empty()){
			int p=Q.front().F,q=Q.front().S;Q.pop();
			for(int i=0;i<4;i++)
				if(p+x[i] && p+x[i]<=n && q+y[i] && q+y[i]<=m && d[p][q]+1<d[p+x[i]][q+y[i]]){
					d[p+x[i]][q+y[i]]=d[p][q]+1;
					QQ.push({{p+x[i],q+y[i]},{0,0}});
				}
		}
		while(!QQ.empty()){
			int p=QQ.front().F.F,q=QQ.front().F.S;
			pii val=QQ.front().S;
			QQ.pop();
			Q.push({p,q});
			for(int i=0;i<4;i++)
				if(p+x[i] && p+x[i]<=n && q+y[i] && q+y[i]<=m && d[p][q]<d[p+x[i]][q+y[i]] && ((val.F+abs(x[i])<k && val.S+abs(y[i])<k) || s[p+x[i]][q+y[i]]=='.')){
					d[p+x[i]][q+y[i]]=d[p][q];
					QQ.push({{p+x[i],q+y[i]},{val.F+abs(x[i]),val.S+abs(y[i])}});
				}
		}
	}
}
 
int main(){
	FastIO
 
	cin >> n >> m >> k >> xs >> ys >> xt >> yt;
	for(int i=1;i<=n;i++){
		cin >> s[i];
		s[i]='#'+s[i];
		d[i].resize(m+1);
	}
	bfs();
	cout << d[xt][yt] << endl;
 
	return 0;
}

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