QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#49880 | #3832. Robert Floyd | ckiseki# | AC ✓ | 45ms | 13168kb | C++20 | 2.7kb | 2022-09-23 19:26:45 | 2022-09-23 19:26:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2077;
bool V[maxn][maxn], H[maxn][maxn];
bool vis[maxn][maxn];
bool ok(int i, int j) {
return i >= 0 && i < maxn && j >= 0 && j < maxn;
}
void bfs(int ii, int jj) {
queue<pair<int, int>> q;
vis[ii][jj] = true;
q.emplace(ii, jj);
auto dfs = [&](int i, int j) {
vis[i][j] = true;
q.emplace(i, j);
};
while (not q.empty()) {
auto [i, j] = q.front(); q.pop();
if (ok(i-1,j) && not vis[i-1][j] && not H[i][j])
dfs(i-1, j);
if (ok(i+1,j) && not vis[i+1][j] && not H[i+1][j])
dfs(i+1, j);
if (ok(i,j-1) && not vis[i][j-1] && not V[i][j])
dfs(i, j-1);
if (ok(i,j+1) && not vis[i][j+1] && not V[i][j+1])
dfs(i, j+1);
}
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
for (int i = 0; i < maxn; i++)
for (int j = 0; j < maxn; j++)
vis[i][j] = false;
int T;
cin >> T;
while (T--) {
string s;
cin >> s;
int x = 0, y = 0;
int mnx = 1e9, mxx = -1e9;
int mny = 1e9, mxy = -1e9;
vector<pair<int,int>> ver, hor, v;
for (char c: s) {
if (c == 'L') {
x -= 1;
ver.emplace_back(x, y); // (x,y-1) (x,y)
} else if (c == 'R') {
ver.emplace_back(x, y); // (x,y-1) (x,y)
x += 1;
} else if (c == 'U') {
hor.emplace_back(x, y); // (x-1,y) (x,y)
y += 1;
} else if (c == 'D') {
y -= 1;
hor.emplace_back(x, y); // (x-1,y) (x,y)
}
mnx = min(mnx, x);
mxx = max(mxx, x);
mny = min(mny, y);
mxy = max(mxy, y);
v.emplace_back(x, y);
v.emplace_back(x-1, y);
v.emplace_back(x, y-1);
v.emplace_back(x-1, y-1);
}
--mnx, --mny;
--mnx, --mny;
++mxx, ++mxy;
++mxx, ++mxy;
for (auto &[a, b]: ver) {
a -= mnx;
b -= mny;
}
for (auto &[a, b]: hor) {
a -= mnx;
b -= mny;
}
for (auto &[a, b]: v) {
a -= mnx;
b -= mny;
}
for (auto &[a, b]: ver) V[a][b] = true;
for (auto &[a, b]: hor) H[a][b] = true;
for (auto [i, j]: v)
vis[i][j] = false;
int cnt = 0;
for (auto [i, j]: v) {
if (!vis[i][j]) {
bfs(i, j);
++cnt;
}
}
cout << cnt << '\n';
for (auto &[a, b]: ver) V[a][b] = false;
for (auto &[a, b]: hor) H[a][b] = false;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 45ms
memory: 13168kb
input:
30 URDR URDRDLDR URDRDLDRDLULDLDR URDRDLDRDLULDLDRDLULURULDLULDLDR URDRDLDRDLULDLDRDLULURULDLULDLDRDLULURULURDRURULDLULURULDLULDLDR URDRDLDRDLULDLDRDLULURULDLULDLDRDLULURULURDRURULDLULURULDLULDLDRDLULURULURDRURULURDRDLDRURDRURULDLULURULURDRURULDLULURULDLULDLDR URDRDLDRDLULDLDRDLULURULDLULDLDRDLULURU...
output:
1 1 2 5 12 29 68 153 336 725 331 235 333 213 357 249 322 229 342 230 348 231 328 225 366 513 2 2 2 3
result:
ok 30 lines