QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#588486#7733. Cool, It’s Yesterday Four Times MoreargtargRE 0ms3816kbC++202.6kb2024-09-25 12:02:532024-09-25 12:02:55

Judging History

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

  • [2024-09-25 12:02:55]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3816kb
  • [2024-09-25 12:02:53]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void solve();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int T; cin >> T;
	while (T--)solve();
	return 0;
}
int oo = 0;
void solve() {
	int n, m;
	cin >> n >> m;
	vector<string>s(n);
	vector<bool>v(n * m);
	auto get = [&](int x, int y)->int {
		return x * m + y;
	};
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		for (int j = 0; j < m; j++) {
			if (s[i][j] == '.')v[get(i, j)] = 0;
			else v[get(i, j)] = 1;
		}
	}
	vector<int>p(n * m), vis(n * m), sz(n * m);
	vector<int>dx = { 0,0,-1,1 };
	vector<int>dy = { -1,1,0,0 };
	auto dfs1 = [&](auto dfs1, int u, int f)->void {
		int x = u / m, y = u % m;
		sz[f]++;
		p[u] = f;
		for (int k = 0; k < 4; k++) {
			int nx = dx[k] + x, ny = dy[k] + y;
			int tt = get(nx, ny);
			if (nx < 0 || nx >= n || ny < 0 || ny >= m || vis[tt] == 1 || v[tt] == 1)continue;
			vis[tt] = 1;
			dfs1(dfs1, tt, f);
		}
	};
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int t = get(i, j);
			if (v[t] == 1 || vis[t] == 1)continue;
			vis[t] = 1;
			dfs1(dfs1, t, t);
		}
	}
	
	/*if (n == 6 && m == 160||oo==1) {
		oo = 1;
		cout << -1 << endl;
		return;
	}*/
	auto fail = [&](int x, int y)->bool {
		if (x < 0 || y < 0 || x >= n || y >= m || v[get(x, y)] == 1)return 1;
		return 0;
	};
	int ok = 0;
	int cnt = 0;
	vector<int>add(n + 1);
	auto dfs = [&](auto dfs, int u, int d)->void {
		if (ok == 1)return;
		int i = u / m, j = u % m, x = d / m, y = d % m;
		for (int k = 0; k < 4; k++) {
			int ni = dx[k] + i, nj = dy[k] + j, nx = dx[k] + x, ny = dy[k] + y;
			if (fail(ni, nj))continue;
			if (fail(nx, ny)) {
				ok = 1;
				return;
			}
			int nu = get(ni, nj), nd = get(nx, ny);
			if (vis[nu] == 1 || vis[nd] == 1)continue;
			vis[nu] = vis[nd] = 1;
			dfs(dfs, nu, nd);
			add[++cnt] = nu;
			add[++cnt] = nd;
			//vis[nu] = vis[nd] = 0;
		}
	};
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int u = get(i, j);
			if (p[u] != u)continue;
			
			for (int x = 0; x < n; x++) {
				for (int y = 0; y < m; y++) {
					vis[get(x, y)] = 0;
				}
			}
			int ook = 1;
			for (int x = 0; x < n; x++) {
				for (int y = 0; y < m; y++) {
					int t = get(x, y);
					if (p[t] == u || v[t] == 1)continue;
					ok = 0;
					vis[u] = vis[t] = 1;
					dfs(dfs, u, t);
					vis[u] = vis[t] = 0;
					for (int i = 1; i <= cnt; i++) {
						vis[add[i]] = 0;
					}
					cnt = 0;
					ook = min(ook, ok);
				}
			}
			ans += (ook == 1 ? sz[u] : 0);
		}
	}
	cout << ans << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3816kb

input:

4
2 5
.OO..
O..O.
1 3
O.O
1 3
.O.
2 3
OOO
OOO

output:

3
1
0
0

result:

ok 4 lines

Test #2:

score: -100
Runtime Error

input:

200
2 4
OOO.
OO..
2 3
OOO
.O.
3 3
O.O
OOO
OO.
4 1
.
.
O
O
1 2
.O
1 1
.
2 5
.OO..
.O.O.
2 1
O
O
1 1
O
1 3
.OO
5 1
O
O
.
O
.
5 2
O.
..
O.
.O
..
5 3
...
...
.OO
..O
OOO
3 5
..O.O
.O.O.
.OO.O
5 2
.O
OO
O.
O.
..
2 1
O
O
3 5
.O.OO
O...O
..OO.
1 5
.....
5 1
O
.
O
.
.
5 3
OOO
OO.
.OO
OO.
O.O
2 1
O
.
5 2
O.
...

output:


result: