Submission #1094377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094377		stefanopulos	Maze (JOI23_ho_t3)	C++17	100 / 100	641 ms	175952 KiB

Main

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ldb;
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ldb,ldb> pdd;

#define ff(i,a,b) for(int i = a; i <= b; i++)
#define fb(i,b,a) for(int i = b; i >= a; i--)
#define trav(a,x) for(auto& a : x)
 
#define sz(a) (int)(a).size()
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

const int mod = 1000000007;
const int inf = 1e9 + 5;
const int mxN = 200005; 

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

int n, m, k;
int sX, sY;
int gX, gY;

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m >> k >> sX >> sY >> gX >> gY;
    vector<string> s(n + 1);
    ff(i,1,n)cin >> s[i], s[i] = ' ' + s[i];

    vector<vector<bool>> used(n + 1, vector<bool>(m + 1));
    ff(i,1,n)ff(j,1,m)used[i][j] = 0;

    vector<vector<pii>> cale(n + 1, vector<pii>(m + 1));

    int cur = 0; queue<pii> que; que.push({sX, sY});
    while(1){

        vector<pii> A;
        while(sz(que)){
            auto [x, y] = que.front(); que.pop(); A.pb({x, y});
            ff(i,0,3){
                int nwx = x + dx[i];
                int nwy = y + dy[i];
                if(nwx >= 1 && nwx <= n && nwy >= 1 && nwy <= m && s[nwx][nwy] == '.'){
                    if(!used[nwx][nwy]){
                        used[nwx][nwy] = 1;
                        que.push({nwx, nwy});
                    }
                }
            }
        }

        vector<pii> vec;
        for(auto [x, y] : A){
            if(x == gX && y == gY){
                cout << cur << '\n';
                return 0;
            }

            ff(i,0,3){
                int nwx = x + dx[i];
                int nwy = y + dy[i];
                if(nwx >= 1 && nwx <= n && nwy >= 1 && nwy <= m && s[nwx][nwy] == '#'){
                    if(!used[nwx][nwy]){
                        que.push({nwx, nwy}); cale[nwx][nwy] = {nwx, nwy};
                        used[nwx][nwy] = 1;
                    }
                }
            }

        }

        queue<pii> temp;
        while(sz(que)){
            auto [x, y] = que.front(); que.pop(); temp.push({x, y});
            ff(i,0,3){
                int nwx = x + dx[i];
                int nwy = y + dy[i];
                if(nwx >= 1 && nwx <= n && nwy >= 1 && nwy <= m){
                    if(!used[nwx][nwy] && abs(nwx - cale[x][y].fi) < k && abs(nwy - cale[x][y].se) < k){
                        used[nwx][nwy] = 1; cale[nwx][nwy] = cale[x][y];
                        que.push({nwx, nwy});
                    }
                }
            }
        }

        swap(que, temp); cur += 1; 

    }

    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
...............

// probati bojenje sahovski
*/
 
 
 
 
 

• 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