QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#488025	#7733. Cool, It’s Yesterday Four Times More	Gaze	TL	56ms	200996kb	C++14	2.2kb	2024-07-23 15:15:03	2024-07-23 15:15:04

Judging History

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

[2024-07-23 15:15:04]
评测

测评结果：TL
用时：56ms
内存：200996kb

查看

[2024-07-23 15:15:03]
提交

answer

#include<bits/stdc++.h>
using namespace std;
struct Node {
	int n, m;
}str[5010];
int T, n, m, opt;
char ch;
int e[5010][5010], vis[5010][5010], win[5010];
void DFS(int x, int y, int num) {
	if(vis[x][y] != 0 || e[x][y] == 0) return;
	vis[x][y] = num;
	DFS(x + 1, y, num);
	DFS(x, y + 1, num);
	DFS(x - 1, y, num);
	DFS(x, y - 1, num);
}
bool v[5010][5010];
void clear(int x, int y) {
	if(v[x][y] == 0) return;
	v[x][y] = 0;
	clear(x + 1, y);
	clear(x - 1, y); 
	clear(x, y + 1); 
	clear(x, y - 1);
}
void cmp(int x, int y, int xa, int yb) {
	if(opt == 0 || v[x][y] == 1) return;
    if(e[x][y] == 0) return;
	if(e[xa][yb] == 0) {
		opt = 0;
		return;
	}
	v[x][y] = 1;
	cmp(x + 1, y, xa + 1, yb);
	cmp(x - 1, y, xa - 1, yb); 
	cmp(x, y + 1, xa, yb + 1); 
	cmp(x, y - 1, xa, yb - 1); 
	return;
}
void Solve() {
	int num = 0;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			if(e[i][j] == 1 && vis[i][j] == 0) {
				num += 1;
				DFS(i, j, num);
			}
		}
	}
//	for(int i = 1; i <= n; ++i) {
//		for(int j = 1; j <= m; ++j) {
//			cout << vis[i][j];
//		}
//		cout << endl;
//	}
    for(int i = 1; i <= n; ++i) {
    	for(int j = 1; j <= m; ++j) {
    		int nm = vis[i][j];
    		if(nm == 0) continue;
    		if(str[nm].n == 0) {
    			str[nm].n = i;
    			str[nm].m = j;
			}
		}
	}
	for(int i = 1; i <= num; ++i) {
		int op = 0;
		for(int j = 1; j <= n; ++j) {
			for(int k = 1; k <= m; ++k) {		
				if(vis[j][k] != i && e[j][k] == 1) {
                    clear(str[i].n, str[i].m);
					opt = 1;
					cmp(str[i].n, str[i].m, j, k);
					op = max(opt, op);
				}
			}
		}
		if(op == 0) {
			win[i] = 1;
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			if(win[vis[i][j]] == 1) ans += 1;
		}
	}
	cout << ans << endl;
}
int main() {
	//freopen("1.in", "r", stdin);
	cin >> T;
	for(int i = 1; i <= T; ++i) {
		memset(e, 0, sizeof(e));
		memset(vis, 0, sizeof(vis));
		memset(win, 0, sizeof(win));
		memset(str, 0, sizeof(str));
		cin >> n >> m;
		for(int i = 1; i <= n; ++i) {
			for(int j = 1; j <= m; ++j) {
				cin >> ch;
				if(ch == '.') e[i][j] = 1;
			}
		}
		Solve();
    }
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 56ms

memory: 200996kb

input:

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

output:

result:

ok 4 lines

Test #2:

score: -100

Time Limit Exceeded

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: