# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1117157 | pedroslrey | Land of the Rainbow Gold (APIO17_rainbow) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> M;
void init(int n, int m, int sx, int sy, int sl, char *serp) {
M.assign(n, vector<int>(m));
--sx; --sy;
map<char, int> sdx{{'N', -1}, {'S', 1}};
map<char, int> sdy{{'W', -1}, {'E', 1}};
M[sx][sy] = true;
for (int i = 0; i < sl; ++i) {
char c = serp[i];
sx += sdx[c]; sy += sdy[c];
M[sx][sy] = -1;
}
// int comp = 0;
// pref.assign(n, vector<int>(m));
// for (int i = 0; i < n; ++i)
// for (int j = 0; j < m; ++j)
// if (M[i][j] == 0) {
// pref[i][j] = 1;
// pos.emplace_back(i, j);
// dfs(i, j, ++comp);
// }
// for (int i = 0; i < n; ++i)
// for (int j = 0; j < m; ++j)
// pref[i][j] += (i > 0 ? pref[i-1][j] : 0)
// + (j > 0 ? pref[i][j-1] : 0)
// - (i > 0 && j > 0 ? pref[i-1][j-1] : 0);
}
// int grid_sum(int x1, int y1, int x2, int y2) {
// return pref[x2][y2]
// - (x1 > 0 ? pref[x1 - 1][y2] : 0)
// - (y1 > 0 ? pref[x2][y1 - 1] : 0)
// + (x1 > 0 && y1 > 0 ? pref[x1 - 1][y1 - 1] : 0);
// }
int colours(int x1, int y1, int x2, int y2) {
--x1; --y1; --x2; --y2;
static int cnt = 0;
function<void (int, int)> dfs = [&](int x, int y) {
M[x][y] = cnt;
static vector<int> dx{1, 0, -1, 0};
static vector<int> dy{0, 1, 0, -1};
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k], ny = y + dy[k];
if (nx < x1 || nx > x2 || ny < y1 || ny > y2) continue;
if (M[nx][ny] == cnt || M[nx][ny] == -1) continue;
dfs(nx, ny);
}
};
++cnt;
int ans = 0;
for (int i = x1; i <= x2; ++i)
for (int j = y1; j <= y2; ++j)
if (M[i][j] != -1 && M[i][j] != cnt) {
++ans;
dfs(i, j);
}
return ans;
}