ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#200505 | #536. 打地鼠 | tkswls | 100 | 247ms | 9164kb | C++11 | 1.8kb | 2024-01-04 10:50:38 | 2024-01-04 12:07:22 |
answer
#include <bits/stdc++.h>
using namespace std;
int n, a[1005][1005], b[1005][1005], suml[1005], sumh[1005], h[1005], l[1005], vis[1005][1005], m;
char c;
queue<pair<int, int>> pa;
inline void solve(pair<int, int> p) {
if (!h[p.first]) {
h[p.first] = 1;
for (int i = 1; i <= m; i++) {
if (i == p.second) continue;
b[p.first][i] = -1;
if (!vis[p.first][i] && suml[i] - max(0, b[p.first][i]) == 0) {
pa.push(make_pair(p.first, i));
vis[p.first][i] = 1;
}
}
}
if (!l[p.second]) {
l[p.second] = 1;
for (int i = 1; i <= n; i++) {
if (i == p.first) continue;
b[i][p.second] = -1;
if (!vis[i][p.second] && sumh[i] - max(0, b[i][p.second]) == 0) {
pa.push(make_pair(i, p.second));
vis[i][p.second] = 1;
}
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
bool flg = true, fflg = true, ffflg = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> c;
if (c == 'X') a[i][j] = 1;
else a[i][j] = 0, fflg = false;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> c;
if (c == 'X') b[i][j] = 1, sumh[i]++, suml[j]++, ffflg = false;
else b[i][j] = 0;
if (b[i][j] != a[i][j]) flg = 0;
}
}
if (flg) {
cout << 1;
return 0;
}
if (fflg || ffflg) {
cout << 0;
return 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (b[i][j] == 1 && suml[j] == 1 && sumh[i] == 1) pa.push(make_pair(i, j)), vis[i][j] = 1, b[i][j] = -1;
}
}
while (pa.size()) {
pair<int, int> op = pa.front();
pa.pop();
solve(op);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// cout << b[i][j] << ' ';
if (b[i][j] != -1 && a[i][j] != b[i][j]) {
cout << 0;
return 0;
}
}
// cout << "\n";
}
cout << 1;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 0ms
memory: 1304kb
input:
4 4 OOOX XXXX OOXO XXOO OOXX OOOO XOOX XOOX
output:
0
result:
ok "0"
Test #2:
score: 0
Accepted
time: 0ms
memory: 1316kb
input:
4 4 OXXO OXOX XOOX XOOO OOOO OXOO OXXX XOOO
output:
0
result:
ok "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 1312kb
input:
4 4 OOXX XXOX OXOX XXXX XXOO XOXO OOOX XXXO
output:
0
result:
ok "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 1316kb
input:
4 4 XXXX XXOO OXOX XXXO OXXO OOOX XOOO OXXO
output:
1
result:
ok "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 1316kb
input:
4 4 XOOO XXXX XOOX XOXO OXOO XOOO XOOO OOOO
output:
1
result:
ok "1"
Test #6:
score: 0
Accepted
time: 0ms
memory: 1324kb
input:
4 4 OOOO XOOO OOOO OXOX OOXO OOOO OOOX OOOO
output:
1
result:
ok "1"
Subtask #2:
score: 30
Accepted
Test #7:
score: 30
Accepted
time: 0ms
memory: 1664kb
input:
50 50 XOOOOOXOXXOOOOXXOOOXXXXXXOOOOOXOXOXXXXOXOOXXXXXOOO OXOOXOOOOXXOOOOXOOXXXOOXXXXXOXXOXOXXOOOXOXO...
output:
0
result:
ok "0"
Test #8:
score: 0
Accepted
time: 0ms
memory: 1664kb
input:
50 50 XXXXXOXXOOOOXXOXOOXOOOOXXOOOOXOOXOOOXXOOOOOXOXXXOO OXXXOXXXOOXOOXXXOOXOXXXOXOOXOOOXOXXXXXXXXXO...
output:
0
result:
ok "0"
Test #9:
score: 0
Accepted
time: 0ms
memory: 1664kb
input:
50 50 XOOOOOXOOOOXXOXXOXXOOXXOXXOXOXOOOXXXOXXXXOOXOOOXXO OOOOXXXOXOOOXXXXOOXOXXXOOOXXOXOOOXXOXXOOOXX...
output:
0
result:
ok "0"
Test #10:
score: 0
Accepted
time: 0ms
memory: 1688kb
input:
50 50 OOOXXXOOXXOOOXOXOOXXOOXXOOXOXXXXOOXOOOOOXXXOXOOXOO XXXXXOXXXXXXXOOOOXXXOXXXOXOXXXOOXXOOOOOXXXX...
output:
1
result:
ok "1"
Test #11:
score: 0
Accepted
time: 0ms
memory: 1692kb
input:
50 50 OXXOOXOOXXOXXXOOXOXOXXXOXXOXOOOXOOOXOOOOOOOOOOOOXO XXXOOXOOXXXOOOOXOXOOXXXOXOXOXOXOOXXOOOXOXXO...
output:
1
result:
ok "1"
Test #12:
score: 0
Accepted
time: 1ms
memory: 1684kb
input:
50 50 XOOOXXXXOXOXXXXOXOOXXXOOOXXOOXXOOOXXOXXXOOXOOXXOOX OOXXXOXOOXOOOOXXOXXOXOXOOOOOXOOOXOXOOXXXXOO...
output:
1
result:
ok "1"
Subtask #3:
score: 50
Accepted
Test #13:
score: 50
Accepted
time: 46ms
memory: 9136kb
input:
1000 1000 XXOXOOXOOXOXXXXOOOXXOXOXOXXOXOXOOXOOOOXXOOOXOOOOXOOOOOXXOXXXOXOOXXXOXXXOXOOOXXXXOXOOOOOXXO...
output:
0
result:
ok "0"
Test #14:
score: 0
Accepted
time: 37ms
memory: 9140kb
input:
1000 1000 XXOXXOXOXXXOOOXOOOXOOXXXOOOOXXOXXOXXXOOXOXOOOOXXOXXXXXOOOXOXXXXOOOOOXOXOOOXXOXXXXXXOXOXXXO...
output:
0
result:
ok "0"
Test #15:
score: 0
Accepted
time: 39ms
memory: 9136kb
input:
1000 1000 OXOOXXOXXXXXOXXXXXOXXOXOXXXOXOXOOOXOXOOXOOXOXXOXOXXOOXXOXXOXXOXOOXOOXXOOXXXXXOXOXOXOOOOXOX...
output:
0
result:
ok "0"
Test #16:
score: 0
Accepted
time: 42ms
memory: 9144kb
input:
1000 1000 OOOXOXOOOOXOXXOXXOOOXOXXOXXOOOOOXOOOOXXOOOXOOOXXXOOOXOOOOXXOOXXOOOOXOOOXXOXXOXXOOOXXOXOXXX...
output:
1
result:
ok "1"
Test #17:
score: 0
Accepted
time: 42ms
memory: 9164kb
input:
1000 1000 XXOXXXXXXXXXOXOOXOXOOXXXOOOOOOOOOXOXOOXOXXOOOXXOXOXOOXOOXOXOXOXXXOXOXXXXOOXXXXOXOXOOXXXXOX...
output:
1
result:
ok "1"
Test #18:
score: 0
Accepted
time: 40ms
memory: 9148kb
input:
1000 1000 XXXXXOOOXXOXOOOOXXOOXOOXXOOOXXXXXXXOXXXXXXXOOOXOXOXXXOXXOXXOXXOOOOXOOXOOXOXOOXOOXOOXOXOXXO...
output:
1
result:
ok "1"
Extra Test:
score: 0
Extra Test Passed