Submission #1324794

#TimeUsernameProblemLanguageResultExecution timeMemory
1324794comet0Maze (JOI23_ho_t3)C++20
8 / 100
244 ms12444 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
    
    int r, c, n;
    cin >> r >> c >> n;
	int sx, sy, gx, gy; cin >> sx >> sy >> gx >> gy; sx--; sy--; gx--; gy--;
	vector<vector<bool>> grid(r, vector<bool>(c));
	for (int i = 0; i < r; i++) {
		string s; cin >> s;
		for (int j = 0; j < c; j++) grid[i][j] = s[j] == '.';
	}

    vector<vector<int>> dist(r, vector<int>(c, INT_MAX));
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq;

    dist[sx][sy] = 0;
    pq.push({0, sx, sy});
    
    const pair<int, int> dir[4] = {
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1}
	};

    while (!pq.empty()) {
        auto [d, x, y] = pq.top();
        pq.pop();
        if (d != dist[x][y]) continue;

        for (auto [x1, y1] : dir) {
            int nx = x + x1;
            int ny = y + y1;
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;

            int w = grid[nx][ny] ? 0 : 1;
            if (dist[nx][ny] > d + w) {
                dist[nx][ny] = d + w;
                pq.push({dist[nx][ny], nx, ny});
            }
        }
    }

    cout << dist[gx][gy];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...