Submission #935816

#	Time	Username	Problem	Language	Result	Execution time	Memory
935816		anton	Maze (JOI23_ho_t3)	C++17	27 / 100	2101 ms	25248 KiB

Main

#include<bits/stdc++.h>


using namespace std;
#define int long long
#define pii pair<int, int>

int R, C;
int N;

pii debut;
pii fin;

vector<vector<char>> maze;
vector<vector<int>> vis;

pii delta[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

bool is_valid(pii pos){
    if(pos.first>=R || pos.first< 0){
        return false;
    }
    if(pos.second>=C || pos.second<0){
        return false;
    }
    return true;
}

vector<pii> get_free(pii pos){
    vector<pii> res;
    for(auto d: delta){
        pii c= {pos.first+d.first, pos.second+d.second};
        if(is_valid(c) && maze[c.first][c.second] != '#'){
            res.push_back(c);
        }
    }
    return res;
}

vector<pii> get_paid(pii pos){
    vector<pii> res;

    for(int i = pos.first-N; i<=pos.first+N; i++){
        for(int j = pos.second-N; j<=pos.second+N; j++){
            pii c= {i, j};
            if(is_valid(c)){
                if(abs(c.first-pos.first)<=N && abs(c.second-pos.second)<=N){
                    if(abs(c.first-pos.first)<N || abs(c.second-pos.second)<N){
                        res.push_back(c);
                    }
                }
            }
        }
    }

    /*for(int i= -N; i<=N; i+=2*N){
        for(int j = -(N-1); j<=N-1; j++){
            pii c = {pos.first+i, pos.second+j};
            if(is_valid(c)){
                res.push_back(c);
            }
        }
    }

    for(int i= -N; i<=N; i+=2*N){
        for(int j = -(N-1); j<=N-1; j++){
            pii c = {pos.first+j, pos.second+i};
            if(is_valid(c)){
                res.push_back(c);
            }
        }
    }*/
    return res;
}


void display(){
    for(int i = 0; i<R; i++){
        for(int j = 0; j<C; j++){
            if(maze[i][j]=='.'){
                if(vis[i][j]){
                    cout<<'o';
                }
                else{
                    cout<<'.';
                }
            }
            else{
                if(vis[i][j]){
                    cout<<'O';
                }
                else{
                    cout<<'#';
                }
            }
        }
        cout<<endl;
    }
    cout<<endl;
}
int BFS(){
    deque<pair<pii, int>> dq;
    dq.push_back({debut, 0});
    vis[debut.first][debut.second] = 0;

    
    while(dq.size()>0){
        //display();
        auto cur= dq.front();
        dq.pop_front();
        pii cur_pos =cur.first;

        int dist = cur.second;
        if(dist!= vis[cur_pos.first][cur_pos.second]){
            continue;
        }

        //cout<<cur_pos.first<<" "<<cur_pos.second<<" "<<dist<<endl;
        //cout<<dist<<endl;

        if(cur_pos == fin){
            return dist;
        }
        
        for(auto e: get_free(cur_pos)){
            if(vis[e.first][e.second] > dist){
                vis[e.first][e.second] = dist;
                dq.push_front({e, dist});
            }
        }

        for(auto e: get_paid(cur_pos)){
            if(vis[e.first][e.second]>dist+1){
                vis[e.first][e.second] = dist+1;
                dq.push_back({e, dist+1});
            }
        }
    }
    return 1e9;

}

signed main(){
    cin>>R>>C;
    cin>>N;

    maze.resize(R, vector<char> (C));
    vis.resize(R, vector<int>(C, 1e9));

    cin>>debut.first>>debut.second;
    debut.first--;
    debut.second--;
    cin>>fin.first>>fin.second;
    fin.first--;
    fin.second--;

    
    for(int i = 0; i<R; i++){
        for(int j = 0; j<C; j++){
            cin>>maze[i][j];
        }
    }

    cout<<BFS()<<endl;

}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 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