Submission #1332727

#TimeUsernameProblemLanguageResultExecution timeMemory
1332727Mauricio_CruzMaze (JOI23_ho_t3)C++20
43 / 100
2095 ms2162688 KiB
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()

#define srtl(x)sort(all(x))
#define srtg(x)sort((x).begin(),(x).end(),greater<>())
#define rev(x) reverse(all(x))
#define lb(x,y) lower_bound(x.begin(),x.end(),y)-x.begin()
#define ub(x,y) upper_bound(x.begin(),x.end(),y)-x.begin()

#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define f first
#define s second
#define pb push_back
#define ins insert
#define next next_permutation
#define _b __builtin_popcount

#define ve vector
#define pii pair<int,int>
#define piii pair<int,pii>
#define vi vector<int>
#define vii vector<pii>
#define viii vector<piii>
#define vvi vector<vi>
//#define vs vector<string>
#define vb vector<bool>

#define pV(x)for(auto i:x)cout<<i<<" ";

#define geta(a){for(auto &i:a)cin>>i;}

#define fr(n)for(int i=0;i<n;i++)
#define Fr(n)for(int i=n-1;i>=0;i--)

#define suma(a)accumulate(a.begin(),a.end(),0LL)

#define br(x){cout<<x<<"\n";return;}
#define yesn cout<<"YES\n";

#define yes()br("YES");
#define no(){br("NO")}

#define alice() br("Alice");
#define bob() br("Bob");

#define cn continue;

#define cint const int
#define int long long


int mod=1000000007;
cint mod1=100000007;
cint mod2=998244353;

int ax[8]={0,1,0,-1,-1,1,1,-1};
int ay[8]={1,0,-1,0,1,-1,1,-1};

//int euc(int a,int b,int c,int d){return abs(a-c)+abs(b-d);}

int bp(int x,int y){
	if(y==0)return 1;
	int r=bp(x,y/2);
	return (y&1)?r*r%mod*x%mod:r*r%mod;
}
int bpm(int x,int y){
	if(y==0)return 1;
	int r=bp(x,y/2);
	return (y&1)?r*r*x:r*r;
}

int cinn(){
	int n;
	cin>>n;
	return n;
}
#define w cinn()
int n,m,k;
bool on(int x,int y){return (x>=0&&x<n&&y>=0&&y<m);}

int xa,xb;
int ya,yb;

vvi ans;
ve<string>v;

ve<ve<ve<pair<pii,int>>>>adj;

void rec(int xx,int yy){
	queue<pii>q;
	q.push({xx,yy});
	
	while(!q.empty()){
		auto [x,y]=q.front();q.pop();
		for(pair<pii,int>p:adj[x][y]){
			if(ans[p.f.f][p.f.s]>ans[x][y]+p.s){
				ans[p.f.f][p.f.s]=ans[x][y]+p.s;
				q.push(p.f);
			}
		}
	}
}

void solve(){
	cin>>n>>m>>k;
	adj=ve<ve<ve<pair<pii,int>>>>(n+1,ve<ve<pair<pii,int>>>(m+1));
	cin>>xa>>ya>>xb>>yb;xa--;xb--;ya--;yb--;
	ans=vvi(n+1,vi(m+1,1e18));
	v.resize(n);
	for(auto&i:v)cin>>i;
	
	ans[xa][ya]=0;
	//return;
	for(int x=0;x<n;x++){
		for(int y=0;y<m;y++){
			
			if( (x-k<=xb&&xb<=x+k && y-k<=yb&&yb<=y+k ) &&
			(x+k!=xb||y+k!=yb) &&
			(x+k!=xb||y-k!=yb) &&
			(x-k!=xb||y+k!=yb) &&
			(x-k!=xb||y-k!=yb)
			){
				adj[x][y].pb({{xb,yb},1});
			}
			
			fr(4){
				int X=x+ax[i],Y=y+ay[i];
				if(on(X,Y)&&v[X][Y]=='.'){
					adj[x][y].pb({{X,Y},0});
				}
			}
			
			for(int j=(-k)+1;j<k;j++){
				int X=x-k,Y=y+j;
				if(!on(X,Y))cn;
				adj[x][y].pb({{X,Y},1});
			}
			for(int j=(-k)+1;j<k;j++){
				int X=x+k,Y=y+j;
				if(!on(X,Y))cn;
				adj[x][y].pb({{X,Y},1});
			}
			
			for(int j=(-k)+1;j<k;j++){
				int X=x+j,Y=y-k;
				if(!on(X,Y))cn;
				adj[x][y].pb({{X,Y},1});
			}
			for(int j=(-k)+1;j<k;j++){
				int X=x+j,Y=y+k;
				if(!on(X,Y))cn;
				adj[x][y].pb({{X,Y},1});
			}
			
			
			
		}
	}
	
	rec(xa,ya);
	
	cout<<ans[xb][yb];
	
	//cerr<<"\n\n\n";
	fr(n){
	//	for(int j:ans[i])cout<<j<<" ";cout<<"\n";
	}
	
}

int32_t main(){
	
	ios;

	int t=1;
	//cin>>t;
	
	while(t--){
		solve();
	}
	
	return 0;
}
/*
2 4 2
1 1
2 4
.###
###.

6 6 1
1 6
6 1
..#.#.
##.###
####.#
...###
##.##.
.#.###

6 7 6
6 4
3 1
..#.#.#
##.##..
.######
#..#.#.
.######
..#.##.

1 15 1
1 15
1 1
...............

6 6 1
1 6
6 3
..###.
.#.#..
#..##.
.##..#
#.###.
##.#.#
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...