From e47c57a92d07f40d792b4a22c9934e0502c75aad Mon Sep 17 00:00:00 2001 From: Syndamia Date: Sun, 21 May 2023 20:14:51 +0300 Subject: [DAAP] Added exercises from second exam --- .../Practicum/Exam2/1-Office-FirstTry.cpp | 129 +++++++++++++++++++++ 1 file changed, 129 insertions(+) create mode 100644 Year 2/Design and analysis of algorithms/Practicum/Exam2/1-Office-FirstTry.cpp (limited to 'Year 2/Design and analysis of algorithms/Practicum/Exam2/1-Office-FirstTry.cpp') diff --git a/Year 2/Design and analysis of algorithms/Practicum/Exam2/1-Office-FirstTry.cpp b/Year 2/Design and analysis of algorithms/Practicum/Exam2/1-Office-FirstTry.cpp new file mode 100644 index 0000000..00e5eab --- /dev/null +++ b/Year 2/Design and analysis of algorithms/Practicum/Exam2/1-Office-FirstTry.cpp @@ -0,0 +1,129 @@ +#include +#include +#include +#include +#include +#include +using namespace std; + +/* + * .....# 6 + 7 + 8 + 9 + 10 = 21 + 19 = 40 + * .###.# 5 + * ...#.# 4 + 5 + 6 = 15 + * .##### 3 + * ..^..# 2 + 1 + 0 + 1 + 2 = 6 + * ###### + * + * +3 3 1 +.## +... +##. +1 1 + + +10 10 10 ++.####...# +####.#.##. +...#....## +.###...... +###.....#. +..#....... +##.......# +..#.##.### +...###.##. +.#...#...# +1 1 +1 7 +2 10 +3 1 +6 1 +8 1 +9 10 +10 8 +5 2 +1 3 + + + */ + +typedef pair loc; + +long long N, M, K; +loc dir[] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}}; + +loc operator+(const loc& p1, const loc& p2) { + return { p1.first + p2.first, p1.second + p2.second }; +} + + +vector> djikstra(loc s, vector& matrix) { + priority_queue, vector>, less>> q; + vector> visited(N, vector(M)); + vector> dist(N, vector(M, -1)); + dist[s.first][s.second] = 0; + q.push({ 0, s }); + while (!q.empty()) { + loc c = q.top().second; + q.pop(); + + visited[c.first][c.second] = true; + for (int i = 0; i < 4; i++) { + loc ne = c + dir[i]; + if (0 > ne.first || ne.first >= N || 0 > ne.second || ne.second >= M || visited[ne.first][ne.second] || matrix[ne.first][ne.second] == '#') continue; + + if (dist[ne.first][ne.second] == -1 || dist[c.first][c.second] + 1 < dist[ne.first][ne.second]) { + dist[ne.first][ne.second] = dist[c.first][c.second] + 1; + q.push({ dist[ne.first][ne.second], ne}); + } + } + } + return dist; +} + +int main() { + ios::sync_with_stdio(false); + cin.tie(NULL); + cout.tie(NULL); + + cin >> N >> M >> K; + string s; + vector matrix; + for (long long i = 0; i < N; i++) { + cin >> s; + matrix.push_back(s); + } + vector> food; + for (long long i = 0; i < K; i++) { + long long ri, ci; + cin >> ri >> ci; + food.push_back({ri-1, ci-1}); + } + + long long sum = 0; + for (long long i = 0; i < N; i++) { + for (long long j = 0; j < M; j++) { + if (matrix[i][j] == '#') continue; + + vector> dist = djikstra({i,j}, matrix); + // cout << endl << i << " " << j << " is at" << endl; + // for (long long i = 0; i < N; i++) { + // for (long long j = 0; j < M; j++) { + // cout << i << " " << j << " dist " << dist[i][j] << endl; + // } + // } + long long mind = -1; + for (auto f : food) { + if (matrix[f.first][f.second] == '#') continue; + if (mind == -1) { + mind = dist[f.first][f.second]; + continue; + } + mind = min(mind, dist[f.first][f.second]); + } + // cout << "mind " << mind << endl; + sum += mind; + } + } + cout << sum << endl; +} -- cgit v1.3.1-26-gb76a