QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#590844 | #833. Cells Blocking | caijianhong | TL | 2ms | 16100kb | C++23 | 2.3kb | 2024-09-26 12:01:37 | 2024-09-26 12:01:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
int n, m, cntany = 0, cntf = 0;
bool a[3010][3010], vis[3010][3010], ok[3010][3010];
void bfs0() {
memset(vis, false, sizeof vis);
queue<pair<int, int>> q;
if (!a[1][1]) q.emplace(1, 1), vis[1][1] = true;
while (!q.empty()) {
int x = q.front().first, y = q.front().second; q.pop();
if (x < n && !vis[x + 1][y] && !a[x + 1][y]) q.emplace(x + 1, y), vis[x + 1][y] = true;
if (y < m && !vis[x][y + 1] && !a[x][y + 1]) q.emplace(x, y + 1), vis[x][y + 1] = true;
}
if (!vis[n][m]) cout << 1ll * cntf * (cntf - 1) / 2 << endl, exit(0);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) if (!a[i][j] && !vis[i][j]) a[i][j] = true, cntany += 1;
}
}
bool check() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) vis[i][j] = false;
}
queue<pair<int, int>> q;
if (!a[1][1]) q.emplace(1, 1), vis[1][1] = true;
while (!q.empty()) {
int x = q.front().first, y = q.front().second; q.pop();
if (x < n && !vis[x + 1][y] && !a[x + 1][y]) q.emplace(x + 1, y), vis[x + 1][y] = true;
if (y < m && !vis[x][y + 1] && !a[x][y + 1]) q.emplace(x, y + 1), vis[x][y + 1] = true;
}
return !vis[n][m];
}
int main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char ch;
cin >> ch;
if (ch == '*') a[i][j] = true;
else cntf += 1;
}
}
bfs0();
LL ans = 0;
int cntd = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) if (!a[i][j]) {
a[i][j] = true;
if (check()) ans += cntf - 1 + cntany, ok[i][j] = true, cntd += 1;
a[i][j] = false;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) if (!a[i][j] && !ok[i][j]) {
a[i][j] = true;
ans += cntd;
for (int i2 = 1; i2 <= n; i2++) {
for (int j2 = 1; j2 <= m; j2++) if (!a[i2][j2] && !ok[i2][j2]) {
a[i2][j2] = true;
if (check()) ans += 1;
a[i2][j2] = false;
}
}
a[i][j] = false;
}
}
assert(ans % 2 == 0);
cout << ans / 2 << endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 14064kb
input:
3 3 ... ... ...
output:
17
result:
ok 1 number(s): "17"
Test #2:
score: 0
Accepted
time: 0ms
memory: 13892kb
input:
3 3 .** .*. ...
output:
15
result:
ok 1 number(s): "15"
Test #3:
score: 0
Accepted
time: 2ms
memory: 13796kb
input:
3 4 **** .... ****
output:
6
result:
ok 1 number(s): "6"
Test #4:
score: 0
Accepted
time: 0ms
memory: 13840kb
input:
5 5 *.... .*.*. ***** *.*** ..*..
output:
66
result:
ok 1 number(s): "66"
Test #5:
score: 0
Accepted
time: 2ms
memory: 16100kb
input:
10 10 ...***.*.. **...*.*** ...***.*.. .**...*.*. .*****..*. ..*.****.* .**...**** ..*..*.*.* *.*.**.... ....**...*
output:
1378
result:
ok 1 number(s): "1378"
Test #6:
score: -100
Time Limit Exceeded
input:
3000 3000 .....................................................................................................................................................................................................................................................................................................