QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#590844#833. Cells BlockingcaijianhongTL 2ms16100kbC++232.3kb2024-09-26 12:01:372024-09-26 12:01:37

Judging History

你现在查看的是最新测评结果

  • [2024-09-26 12:01:37]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:16100kb
  • [2024-09-26 12:01:37]
  • 提交

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
.....................................................................................................................................................................................................................................................................................................

output:


result: