UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#200505#536. 打地鼠tkswls100247ms9164kbC++111.8kb2024-01-04 10:50:382024-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