Summary Files Commits Branches @commit @diff @stats
path: root / Year 2 / Design and analysis of algorithms / Practicum / Exam2 / 1-Office-FirstTry.cpp
diff options
context:
space:
mode:
Commite47c57a92d07f40d792b4a22c9934e0502c75aad (patch)
Author
 Syndamia <kamen@syndamia.com>
2023-05-21 20:14:51 +0300
Committer
 Syndamia <kamen@syndamia.com>
2023-05-21 20:14:51 +0300
Files468a0859ad209a3acc9f0f94edd468b00d375639 /Year 2/Design and analysis of algorithms/Practicum/Exam2/1-Office-FirstTry.cpp
uni-projects-e47c57a92d07f40d792b4a22c9934e0502c75aad.tar
uni-projects-e47c57a92d07f40d792b4a22c9934e0502c75aad.tar.gz
uni-projects-e47c57a92d07f40d792b4a22c9934e0502c75aad.zip
Parent6ffcfb17f058217f1353cbfd6fa3e8e9cc9681a4 (diff)
[DAAP] Added exercises from second exam
1 files changed, 129 insertions, 0 deletions
-rw-r--r--Year 2/Design and analysis of algorithms/Practicum/Exam2/1-Office-FirstTry.cpp129
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 <iostream>
+#include <string>
+#include <queue>
+#include <vector>
+#include <algorithm>
+#include <utility>
+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<long long, long long> 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<vector<long long>> djikstra(loc s, vector<string>& matrix) {
+ priority_queue<pair<long long, loc>, vector<pair<long long, loc>>, less<pair<long long, loc>>> q;
+ vector<vector<bool>> visited(N, vector<bool>(M));
+ vector<vector<long long>> dist(N, vector<long long>(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<string> matrix;
+ for (long long i = 0; i < N; i++) {
+ cin >> s;
+ matrix.push_back(s);
+ }
+ vector<pair<long, long>> 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<vector<long long>> 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;
+}