QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#555227#4231. Rafting TripFortitude#TL 0ms3716kbC++231.4kb2024-09-09 20:48:472024-09-09 20:48:48

Judging History

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

  • [2024-09-09 20:48:48]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3716kb
  • [2024-09-09 20:48:47]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define f first
#define s second
using namespace std;
using ll = long long;
using pii = pair <int, int>;
const int N = 500, dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int n, m, ans, cnt, used[N][N];
char a[N][N], was[N][N];
void dfs(int i, int j) {
	if (min(i, j) < 0 || i == n || j == m || a[i][j] == '.' || a[i][j] == '#' || was[i][j])
		return;
	was[i][j] = 1;
	
	vector <pii> cells;
	for (int _ = 0; _ < 4; ++_) {
		int ni = i + dx[_];
		int nj = j + dy[_];
		if (min(ni, nj) >= 0 && ni < n && nj < m && a[ni][nj] == '#') {
			cnt += !used[ni][nj];
			used[ni][nj]++;
		}
	}
	ans = max(ans, cnt);
	
	if (a[i][j] == '>')
		dfs(i, j + 1);
	else if (a[i][j] == '<')
		dfs(i, j - 1);
	else if (a[i][j] == '^')
		dfs(i - 1, j);
	else 
		dfs(i + 1, j);
	
	for (int _ = 0; _ < 4; ++_) {
		int ni = i + dx[_];
		int nj = j + dy[_];
		if (min(ni, nj) >= 0 && ni < n && nj < m && a[ni][nj] == '#') {
			used[ni][nj]--;
			cnt -= !used[ni][nj];
		}
	}
	
	was[i][j] = 0;
}
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (a[i][j] == '.' || a[i][j] == '#')
				continue;
			
			dfs(i, j);
		}
	}
	cout << ans;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 6
v<<<#v
v#v<.>
>>v<<<
..v##^
#<<<.^

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

4 5
>v<<.
^<..#
#...#
.#>^#

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3716kb

input:

4 6
>>v#>v
^#>>^v
^<<#v<
.#^<<#

output:

5

result:

ok single line: '5'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

6 6
^.>>>>
^.....
^....v
^....v
#....v
<<<<#v

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

6 7
^>>>>>v
^.....v
^.#^..v
^.#^<.v
^.....v
^<<<<<<

output:

2

result:

ok single line: '2'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

3 7
>v<<<<#
^<#####
#^<<<<<

output:

6

result:

ok single line: '6'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

3 5
><.v#
##.^#
...#.

output:

3

result:

ok single line: '3'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

7 3
###
#>#
###
...
###
#>.
###

output:

4

result:

ok single line: '4'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

2 2
>.
.#

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

2 2
..
.v

output:

0

result:

ok single line: '0'

Test #11:

score: -100
Time Limit Exceeded

input:

498 498
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<...

output:


result: