Submission #895934

#	Time	Username	Problem	Language	Result	Execution time	Memory
895934		niter	Maze (JOI23_ho_t3)	C++14	8 / 100	271 ms	15004 KiB

Main

#include <bits/stdc++.h>
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define pb push_back
#define ins insert
#define pii pair<int,int>
#define ff first
#define ss second
#define op(x) cerr << #x << " = " << x << endl;
#define opa(x) cerr << #x << " = " << x << ", ";
#define spac cerr << ' ';
#define entr cerr << endl;
#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
#define ARR(x, nnn) cerr << #x << " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
using namespace std;
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
ostream& operator<<(ostream& os, pii A){ os << "[" << A.ff << ", " << A.ss << "]"; }

inline bool check(int i, int j, int n, int m){
    return i >= 0 && j >= 0 && i < n && j < m;
}
const int INF = (int)(1e9);
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
vector<vector<char>> c;
vector<vector<int>> dis;

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    pii s, t;
    cin >> s.ff >> s.ss >> t.ff >> t.ss;
    s.ff--; s.ss--; t.ff--; t.ss--;
    c = vector<vector<char>>(n, vector<char>(m, ' '));
    loop(i,0,n){
        loop(j,0,m){
            cin >> c[i][j];
        }
    }
    priority_queue<pair<int,pii>, vector<pair<int,pii>>, greater<pair<int,pii>>> pq;
    pq.push({0, s});
    dis = vector<vector<int>>(n, vector<int>(m, INF));
    dis[s.ff][s.ss] = 0;
    while(!pq.empty()){
        int nowx = pq.top().ss.ff;
        int nowy = pq.top().ss.ss;
        int nowd = pq.top().ff;
        pq.pop();
        if(nowd != dis[nowx][nowy]) continue;
        loop(d,0,4){
            int nx = nowx + dx[d];
            int ny = nowy + dy[d];
            if(!check(nx, ny, n, m)) continue;
            if(dis[nx][ny] > nowd + (c[nx][ny] == '#')){
                dis[nx][ny] = nowd + (c[nx][ny] == '#');
                pq.push({dis[nx][ny], {nx, ny}});
            }
        }
    }
    cout << dis[t.ff][t.ss] << '\n';

}
/*
*/

Compilation message (stderr)

Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::pair<int, int>)':
Main.cpp:16:84: warning: no return statement in function returning non-void [-Wreturn-type]
   16 | ostream& operator<<(ostream& os, pii A){ os << "[" << A.ff << ", " << A.ss << "]"; }
      |                                                                                    ^

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