Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define X ios_base::sync_with_stdio(false); cin.tie(NULL);
- #define FIXED_FLOAT(x) std::fixed <<std::setprecision(2)<<(x)
- void __print(int x) {cerr << x;}
- void __print(long x) {cerr << x;}
- void __print(long long x) {cerr << x;}
- void __print(unsigned x) {cerr << x;}
- void __print(unsigned long x) {cerr << x;}
- void __print(unsigned long long x) {cerr << x;}
- void __print(float x) {cerr << x;}
- void __print(double x) {cerr << x;}
- void __print(long double x) {cerr << x;}
- void __print(char x) {cerr << '\'' << x << '\'';}
- void __print(const char *x) {cerr << '\"' << x << '\"';}
- void __print(const string &x) {cerr << '\"' << x << '\"';}
- void __print(bool x) {cerr << (x ? "true" : "false");}
- template<typename T, typename V>
- void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
- template<typename T>
- void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
- void _print() {cerr << "]\n";}
- template <typename T, typename... V>
- void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
- #ifndef ONLINE_JUDGE
- #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
- #else
- #define debug(x...)
- #endif
- // long long p = 1e9+7;
- typedef long long ll;
- typedef pair<ll,ll> pl;
- typedef vector<int> VI;
- typedef vector<pair<ll,ll>> VP;
- typedef vector<ll> VL;
- typedef vector<VL> VVL;
- typedef vector<bool> VB;
- // typedef pair<ll, ll> PL;
- typedef unordered_map<ll, ll> UMP;
- #define FOR(i,b,init) for(i=init;i<b;i++)
- #define pb push_back
- #define fi first
- #define se second
- #define mp make_pair
- // typedef unordered_set<ll>;
- // void printa(VI &x,ll n){
- // ll i;
- // FOR(i, n){
- // cout<<x[i]<<" ";
- // }
- // cout<<endl;
- // }
- /////GLOABLS VARS
- ll MOD = 1e9+7;
- ll gmx = 1e6+7;
- VL fact(gmx, 1);
- //////FUNCTIONS
- ll powp(ll val, ll deg)
- {
- // debug(val, deg);
- if (!deg)
- return 1;
- if (deg & 1)
- return (powp(val, deg - 1) * val) % MOD;
- ll res = powp(val, deg >> 1);
- // debug(res);
- return (res * res) % MOD;
- }
- ll mx=1e5+7;
- vector<VL> adj;
- VL sub;
- ll n;
- void dfs(ll r, ll parent){
- sub[r]=1;
- // debug(r,parent);
- for(auto k: adj[r]){
- if(k==parent){continue;}
- dfs(k, r);
- sub[r]+=sub[k];
- }
- return;
- }
- //It is not easy but it can be fun, if you think!!!
- //
- // ll mx = 2*1e5+7;
- // vector<vector<pl>> adj;
- int main(){
- ios::sync_with_stdio(0);
- cin.tie(0);
- // #ifndef ONLINE_JUDGE
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- // #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
- // #endif
- ll n,i,j,m;
- cin>>n>>m;
- pl st,end;
- cin>>st.fi>>st.se>>end.fi>>end.se;
- st.fi--;st.se--;end.fi--;end.se--;
- vector<string>l(n);
- FOR(i,n,0){
- cin>>l[i];
- }
- queue<pl> q, waitq;
- q.push(st);
- vector<VL> vis(n, vector<ll>(m,1e18));
- vis[st.fi][st.se]=0;
- VL dir{1,0,-1};
- // VL magic
- bool flag=false;
- ll mag=0;
- while((q.size()>0) || (waitq.size()>0)){
- if(q.size()==0){
- while(waitq.size()>0){
- pl el=waitq.front(); waitq.pop();
- if(vis[el.fi][el.se]>mag){
- // vis[el.fi][el.se]=vis[el.fi][el.se]-1e18;
- q.push(el);
- // mag++;
- }
- }
- continue;
- }
- pl el=q.front();
- q.pop();
- mag = max(mag, vis[el.fi][el.se]);
- if(el==end){
- break;
- }
- for(auto x:dir){
- for(auto y:dir){
- if(abs(x)==abs(y)){
- continue;
- }
- ll nbx = x+el.fi, nby = y+el.se;
- if((nbx>=n) || (nbx<0) || (nby>=m) || (nby<0)){
- continue;
- }
- if((vis[nbx][nby]>vis[el.fi][el.se]) && l[nbx][nby]=='.'){
- vis[nbx][nby] = vis[el.fi][el.se];
- q.push(mp(nbx,nby));
- }
- }
- }
- for(i=max((ll)0, el.fi-2); i<min(n, el.fi+3);i++){
- for(j=max((ll)0, el.se-2); j<min(m, el.se+3);j++){
- if((vis[i][j]>vis[el.fi][el.se]+1) && (l[i][j]=='.')){
- vis[i][j] = 1+vis[el.fi][el.se];
- waitq.push(mp(i,j));
- }
- }
- }
- }
- // debug(vis);
- if(vis[end.fi][end.se]==1e18){
- cout<<-1;
- }
- else{
- cout<<vis[end.fi][end.se];
- }
- // cout.flush();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement