Submission #1046858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046858		1L1YA	Maze (JOI23_ho_t3)	C++17	100 / 100	420 ms	119396 KiB

Main

#include <bits/stdc++.h>


using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
typedef long double     ld;

#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("tests.in" , "r" , stdin) ;

ll mod = 1e9+7;

const ll INF=1e9+23; 
vector<vector<ll> > dist;

int n, m; 
int k; 

pii st, ft; 

int dx[]={1, -1, 0, 0}; 
int dy[]={0, 0, 1, -1}; 

vector<string> a; 
int main()
{
    fast_io
    cin>>n>>m>>k; 
    dist.resize(n, vector<ll>(m, INF));     k--; 
    cin>>ft.F>>ft.S>>st.F>>st.S; 
    ft.F--; ft.S--; 
    st.F--; st.S--; 
    for (int i=0; i<n; i++){
        string s; cin>>s; 
        a.pb(s); 
        
    }
    queue<pair<pll, pll> > q, qq; 
    dist[ft.F][ft.S]=0; 
    q.push({ft, {0, 0}}); 

    while(!q.empty() || !qq.empty()){
        while(!q.empty()){
            auto pp=q.front(); 
            q.pop(); 
            auto v=pp.F; 
                for (int i=0; i<4; i++){
                    pii u=v; 
                    u.F+=dx[i]; 
                    u.S+=dy[i]; 
                    if(u.F>=0 && u.F<n && u.S>=0 && u.S<m){
                        if(a[u.F][u.S]=='.' && dist[u.F][u.S]>dist[v.F][v.S]){
                            dist[u.F][u.S]=dist[v.F][v.S]; 
                            q.push({u, {0, 0}});
                        }
                        if(a[u.F][u.S]=='#' && dist[u.F][u.S]>dist[v.F][v.S]+1){
                            dist[u.F][u.S]=dist[v.F][v.S]+1; 
                            qq.push({u, {k, k}}); 
                        }
                    }
                }
        }
        while(!qq.empty()){
            auto pp=qq.front(); 
            auto v=pp.F; 
            qq.pop(); 
            if(pp.S.F==0 || pp.S.S==0){

                q.push({v, {0, 0}}); 
            }
            for (int i=0; i<4; i++){
                pii u=v; 
                u.F+=dx[i]; 
                u.S+=dy[i]; 
                pii temp=pp.S; 
                temp.F-=abs(dx[i]); 
                temp.S-=abs(dy[i]); 
                if(temp.F<0 || temp.S<0) continue; 
                
                if(u.F>=0 && u.F<n && u.S>=0 && u.S<m){
                    
                    if(dist[u.F][u.S]>dist[v.F][v.S]){
                        dist[u.F][u.S]=dist[v.F][v.S]; 
                        qq.push({u, temp}); 
                    }

            }
            
        }

        }
    }
    cout<<dist[st.F][st.S]<<endl;

    
}

/*

                if(dist[u.F][u.S]>dist[v.F][v.S]){
                    dist[u.F][u.S]=dist[v.F][v.S]; 
                    q.push_front({u, temp}); 
                }
*/

• 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