QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#555252#4231. Rafting TripFortitude#WA 1ms7988kbC++232.5kb2024-09-09 21:06:542024-09-09 21:06:54

Judging History

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

  • [2024-09-09 21:06:54]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7988kb
  • [2024-09-09 21:06:54]
  • 提交

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 = 550, dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
int n, m, ans, used[N][N];
char a[N][N];
int cnt, c[N][N], col[N][N], timer;
bool ok[N][N], in_cycle[N][N];
vector<pii> gr[N][N];


inline void add(int x, int y){
	if(col[x][y] != timer){
		col[x][y] = timer;
		c[x][y] = 0;
	}
	
	if(!c[x][y]) 
		cnt++;
	c[x][y]++;
}
inline void rem(int x, int y){
	if(c[x][y] == 1)
		cnt--;
	c[x][y]--;
}
void dfs(int i, int j) {
	used[i][j] = 1;
	if(ok[i][j]){
		for (int _ = 0; _ < 4; ++_) {
			int ni = i + dx[_];
			int nj = j + dy[_];
			if (min(ni, nj) >= 1 && ni <= n && nj <= m && a[ni][nj] == '#') {
				add(ni, nj);
			}
		}
	}
	
	ans = max(ans, cnt);
	
	for(auto [x, y] : gr[i][j])
		if(!in_cycle[x][y])
			dfs(x, y);
		
	if(ok[i][j]){
		for (int _ = 0; _ < 4; ++_) {
			int ni = i + dx[_];
			int nj = j + dy[_];
			if (min(ni, nj) >= 1 && ni <= n && nj <= m && a[ni][nj] == '#') {
				rem(ni, nj);
			}
		}
	}
}

int main() {
	ios :: sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> a[i][j];
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(a[i][j] == '.' || a[i][j] == '#')
				continue;
			ok[i][j] = 1;
			int x = i, y = j;
			if(a[x][y] == '^') x--;
			else if(a[x][y] == '>') y++;
			else if(a[x][y] == '<') y--;
			else if(a[x][y] == 'v') x++;
			
			gr[x][y].push_back({i, j});
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (a[i][j] == '.' || a[i][j] == '#' || used[i][j])
				continue;
				
			int x = i, y = j;
			while(!used[x][y]){
				used[x][y] = 1;				
				if(a[x][y] == '.' || a[x][y] == '#' || x < 1 || x > n || y < 1 || y > m)
					break;
				
				if(a[x][y] == '^') x--;
				else if(a[x][y] == '>') y++;
				else if(a[x][y] == '<') y--;
				else if(a[x][y] == 'v') x++;
			}
			
			timer++;
			cnt = 0;
			if(ok[x][y]){
				vector<pii> cells;
				while(!in_cycle[x][y]){
					cells.push_back({x, y});
					in_cycle[x][y] = 1;
					if(a[x][y] == '^') x--;
					else if(a[x][y] == '>') y++;
					else if(a[x][y] == '<') y--;
					else if(a[x][y] == 'v') x++;					
				}
				for(auto [x, y] : cells){
					dfs(x, y);
				}
			}else{
				dfs(x, y);
			}
			
		}
	}
	cout << ans;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 1ms
memory: 7988kb

input:

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

output:

2

result:

ok single line: '2'

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 7672kb

input:

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

output:

2

result:

wrong answer 1st lines differ - expected: '5', found: '2'