Submission #1093796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093796		Abito	Maze (JOI23_ho_t3)	C++17	8 / 100	95 ms	88492 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
//#define int long long
#define ll long long
typedef unsigned long long ull;
using namespace std;
const int N=1300;
int n,m,k,sx,sy,ex,ey,mvx[]={1,0,-1,0},mvy[]={0,1,0,-1};
bool ok(int x,int y){
	return x>=1 && x<=n && y>=1 && y<=m;
}
int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>n>>m>>k>>sx>>sy>>ex>>ey;
	int dis[n+5][m+5],p[n+5][m+5];
	char a[n+5][m+5];
	bool vis[n+5][m+5];
	for (int i=0;i<n+5;i++){
		for (int j=0;j<m+5;j++){
			vis[i][j]=0;
			dis[i][j]=INT_MAX;
			p[i][j]=0;
			if (i && i<=n && j && j<=m) cin>>a[i][j];
		}
	}
	if ((2*k+1)*(2*k+1)<=N){
		deque<pair<int,int>> dq;
		dq.push_front({sx,sy});
		dis[sx][sy]=0;
		while (!dq.empty()){
			int x=dq.front().F,y=dq.front().S;
			dq.pop_front();
			if (vis[x][y]) continue;
			//cout<<x<<' '<<y<<' '<<dis[x][y]<<endl;
			vis[x][y]=1;
			for (int i=0;i<4;i++){
				int nx=mvx[i]+x,ny=mvy[i]+y;
				if (!ok(nx,ny) || a[x][y]!='.') continue;
				if (dis[nx][ny]>dis[x][y]){
					dis[nx][ny]=dis[x][y];
					dq.push_front({nx,ny});
				}
			}
			for (int i=max(1,x-k);i<=min(n,x+k);i++){
				for (int j=max(1,y-k);j<=min(m,y+k);j++){
					if (i==x-k && j==y-k) continue;
					if (i==x-k && j==y+k) continue;
					if (i==x+k && j==y-k) continue;
					if (i==x+k && j==y+k) continue;
					if (dis[i][j]>dis[x][y]+1){
						dis[i][j]=dis[x][y]+1;
						dq.push_back({i,j});
					}
				}
			}
		}
	}
	else{
		vector<pair<int,int>> q;
		dis[sx][sy]=0;
		vis[sx][sy]=1;
		q.pb({sx,sy});
		for (int t=0;t<INT_MAX;t++){
			for (int i=0;i<q.size();i++){
				int x=q[i].F,y=q[i].S;
				dis[x][y]=t;
				for (int j=0;j<4;j++){
					int nx=x+mvx[j],ny=y+mvy[j];
					if (vis[nx][ny] || !ok(nx,ny)) continue;
					dis[nx][ny]=t;
					vis[nx][ny]=1;
					q.pb({nx,ny});
				}
			}
			//for (auto u:q) cout<<u.F<<' '<<u.S<<"	";
			//cout<<endl;
			if (vis[ex][ey]) break;
			for (int i=0;i<n+5;i++) for (int j=0;j<m+5;j++) p[i][j]=0;
			for (int i=0;i<q.size();i++){
				int x=q[i].F,y=q[i].S;
				p[max(1,x-k)][max(1,y-k)]++;
				p[max(1,x-k)][min(m,y+k)+1]--;
				p[min(n,x+k)+1][max(1,y-k)]--;
				p[min(n,x+k)+1][min(m,y+k)+1]--;
				if (x-k>=1 && y-k>=1){
					p[x-k][y-k]--;
					p[x-k+1][y-k]++;
					p[x-k][y-k+1]++;
					p[x-k+1][y-k+1]--;
				}
				if (x-k>=1 && y+k<=m){
					p[x-k][y+k]--;
					p[x-k+1][y+k]++;
					p[x-k][y+k+1]++;
					p[x-k+1][y+k+1]--;
				}
				if (x+k<=n && y-k>=1){
					p[x+k][y-k]--;
					p[x+k+1][y-k]++;
					p[x+k][y-k+1]++;
					p[x+k+1][y-k+1]--;
				}
				if (x+k<=n && y+k<=m){
					p[x+k][y+k]--;
					p[x+k+1][y+k]++;
					p[x+k][y+k+1]++;
					p[x+k+1][y+k+1]--;
				}
			}
			for (int i=1;i<=n;i++){
				for (int j=1;j<=m;j++){
					p[i][j]+=p[i-1][j]+p[i][j-1]-p[i-1][j-1];
					if (p[i][j]>0 && !vis[i][j]) q.pb({i,j}),vis[i][j]=1;
					//cout<<p[i][j]<<' ';
				}//cout<<endl;
			}//cout<<endl;
		}
	}
	cout<<dis[ex][ey]<<endl;
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |    for (int i=0;i<q.size();i++){
      |                 ~^~~~~~~~~
Main.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |    for (int i=0;i<q.size();i++){
      |                 ~^~~~~~~~~

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