diff options
[DAAP] Added exercises from second exam
1 files changed, 115 insertions, 0 deletions
| -rw-r--r-- | Year 2/Design and analysis of algorithms/Practicum/Exam2/1-Office-SecondTry.cpp | 115 |
diff --git a/Year 2/Design and analysis of algorithms/Practicum/Exam2/1-Office-SecondTry.cpp b/Year 2/Design and analysis of algorithms/Practicum/Exam2/1-Office-SecondTry.cpp new file mode 100644 index 0000000..cc9a73e --- /dev/null +++ b/Year 2/Design and analysis of algorithms/Practicum/Exam2/1-Office-SecondTry.cpp @@ -0,0 +1,115 @@ +#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; +loc operator+(const loc& l1, const loc& l2) { + return { l1.first + l2.first, l1.second + l2.second }; +} + +long long N, M, K; +loc dir[] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}}; + + +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); + } + for (long long i = 0; i < K; i++) { + long long ri, ci; + cin >> ri >> ci; + ri--; ci--; + if (matrix[ri][ci] != '#') matrix[ri][ci] = '+'; + } + + 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<bool>> visited(N, vector<bool>(M, false)); + queue<loc> bfs; + bfs.push({ i, j }); + bfs.push({-1, -1}); + long long level = 1; + bool stop = false; + while (!bfs.empty() && !stop) { + if (bfs.front() == loc({-1,-1})) { + level++; + bfs.pop(); + continue; + } + loc c = bfs.front(); + bfs.pop(); + visited[c.first][c.second] = true; + bool added = false; + 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 (matrix[ne.first][ne.second] == '+') { + stop = true; + break; + } + bfs.push(ne); + added = true; + } + if (added) bfs.push({ -1, -1 }); + } + sum += level; + } + } + cout << sum << endl; +} |
