QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#71350#5267. Bricks in the Wallneko_nyaa#RE 2ms3388kbC++202.7kb2023-01-09 20:19:252023-01-09 20:19:28

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-09 20:19:28]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:3388kb
  • [2023-01-09 20:19:25]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

int slv(int n, int m, vector<vector<char>> c) {
	int ans = 0;
	{ // horizontal
		vector<int> consec(m); int maxback = 0;
		for (int i = 0; i < n; i++) {
			// one horizon here only
			int cns = 0, mx = 0;
			for (int j = 0; j < m; j++) {
				if (c[i][j] == '.') {
					cns++;
				} else {
					cns = 0;
				}

				mx = max(mx, cns); 
				ans = max(ans, mx + maxback);
			}

			maxback = max(maxback, mx);
			for (int j = 0; j < m; j++) {
				if (c[i][j] == '.') {
					consec[j]++;
				} else {
					consec[j] = 0;
				}
				maxback = max(maxback, consec[j]);
			}

			// two horizon same
			vector<int> cz; int cs = 0;
			for (int j = 0; j <= m; j++) {
				if (j < m && c[i][j] == '.') {
					cs++;
				} else {
					if (cs > 0) cz.push_back(cs); 
					cs = 0;
				}
			}
			sort(cz.begin(), cz.end(), greater<int>());
			if (cz.size() >= 1) ans = max(ans, cz[0]);
			if (cz.size() >= 2) ans = max(ans, cz[0] + cz[1]);
		}
	}

	{ // vertical
		vector<int> consec(n); int maxback = 0;
		for (int i = 0; i < m; i++) {
			// one vertical here only
			int cns = 0, mx = 0;
			for (int j = 0; j < n; j++) {
				if (c[j][i] == '.') {
					cns++;
				} else {
					cns = 0;
				}

				mx = max(mx, cns); 
				ans = max(ans, mx + maxback);
			}

			maxback = max(maxback, mx);
			for (int j = 0; j < n; j++) {
				if (c[j][i] == '.') {
					consec[i]++;
				} else {
					consec[i] = 0;
				}
				maxback = max(maxback, consec[i]);
			}

			// two vertical same
			vector<int> cz; int cs = 0;
			for (int j = 0; j <= n; j++) {
				if (j < n && c[j][i] == '.') {
					cs++;
				} else {
					if (cs > 0) cz.push_back(cs);
					cs = 0;
				}
			}
			sort(cz.begin(), cz.end(), greater<int>());
			if (cz.size() >= 1) ans = max(ans, cz[0]);
			if (cz.size() >= 2) ans = max(ans, cz[0] + cz[1]);
		}
	}
	return ans;
}

void solve() {
	int n, m; cin >> n >> m;
	vector<vector<char>> c(n, vector<char>(m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> c[i][j];
		}
	}

	int ans = slv(n, m, c);
	// flip left
	for (int i = 0; i < n; i++) {
		for (int j = 0, k = m-1; j < k; j++, k--) {
			swap(c[i][j], c[i][k]);
		}
	}
	ans = max(ans, slv(n, m, c));

	// flip down
	for (int i = 0; i < m; i++) {
		for (int j = 0, k = n-1; j < k; j++, k--) {
			swap(c[j][i], c[k][i]);
		}
	}
	ans = max(ans, slv(n, m, c));

	// flip left
	for (int i = 0; i < n; i++) {
		for (int j = 0, k = m-1; j < k; j++, k--) {
			swap(c[i][j], c[i][k]);
		}
	}
	ans = max(ans, slv(n, m, c));
	
	cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	int t; cin >> t;
	while (t--) {
		solve();
	}	

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3388kb

input:

5
2 2
..
..
4 5
###.#
#....
.##.#
#.#.#
2 1
.
.
2 3
###
#.#
5 4
##.#
..#.
#.#.
....
#.##

output:

4
6
2
1
7

result:

ok 5 number(s): "4 6 2 1 7"

Test #2:

score: -100
Dangerous Syscalls

input:

10000
1 6
..#..#
5 7
#..##.#
..###.#
.####..
.##.##.
..#.#.#
1 7
#.####.
10 5
##..#
###.#
....#
#.#..
##.##
###.#
#....
##.##
...##
.....
1 2
.#
1 3
##.
7 6
####..
#####.
#...#.
..#..#
..##.#
##.#..
#..##.
5 4
..##
..#.
..##
..#.
##.#
5 6
.##..#
.#....
##.#.#
#..###
##....
1 6
.#.###
1 2
##
5 5
##.....

output:


result: