Submission #875615

#	Time	Username	Problem	Language	Result	Execution time	Memory
875615		hmm789	Maze (JOI23_ho_t3)	C++14	51 / 100	2000 ms	2097152 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 998244353
 
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int r, c, n, sr, sc, gr, gc;
    cin >> r >> c >> n >> sr >> sc >> gr >> gc;
    sr--; sc--; gr--; gc--;
    string s[r];
    for(int i = 0; i < r; i++) cin >> s[i];
    vector<pair<pair<int, int>, int>> adj[r][c];
    int dx[4] = {-1, 0, 0, 1};
    int dy[4] = {0, -1, 1, 0};
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            for(int k = 0; k < 4; k++) {
                int nx = i+dx[k], ny = j+dy[k];
                if(nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
                if(s[nx][ny] == '#') continue;
                adj[i][j].push_back({{nx, ny}, 0});
            }
            for(int k = -(n-1); k <= n-1; k++) {
                for(int l = 0; l < 4; l++) {
                    int nx = i+dx[l]*n+k*dy[l], ny = j+dy[l]*n+k*dx[l];
                    if(nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
                    adj[i][j].push_back({{nx, ny}, 1});
                }
            }
        }
    }
    for(int i = -n; i <= n; i++) {
        for(int j = -n; j <= n; j++) {
            if(abs(i*j) == n*n || i == 0 && j == 0) continue;
            int nx = gr+i, ny = gc+j;
            if(nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            adj[nx][ny].push_back({{gr, gc}, 1});
        }
    }
    deque<pair<int, pair<int, int>>> dq;
    int dist[r][c];
    memset(dist, -1, sizeof(dist));
    dist[sr][sc] = 0;
    dq.push_front({0, {sr, sc}});
    while(!dq.empty()) {
        pair<int, pair<int, int>> cur = dq.front();
        dq.pop_front();
        if(cur.first != dist[cur.second.first][cur.second.second]) continue;
        for(auto it : adj[cur.second.first][cur.second.second]) {
            if(dist[it.first.first][it.first.second] == -1 || dist[it.first.first][it.first.second] > cur.first+it.second) {
                dist[it.first.first][it.first.second] = cur.first+it.second;
                if(it.second == 0) dq.push_front({cur.first+it.second, it.first});
                else dq.push_back({cur.first+it.second, it.first});
            }
        }
    }
    cout << dist[gr][gc];
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:37:42: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   37 |             if(abs(i*j) == n*n || i == 0 && j == 0) continue;
      |                                   ~~~~~~~^~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 0 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6