1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| int Solution::solve(vector<vector<int>> &A) {
int n = A.size(), m = A[0].size();
vector<vector<int>> vis(n,vector<int>(m));
queue<array<int,3>> q;
auto push = [&](int mask, int y, int x) {
if(!(vis[y][x] & mask)) {
q.push({mask, y, x});
vis[y][x] |= mask;
}
};
for(int i = 0; i < m; i++) {
push(1,0,i);
push(2,n-1,i);
}
for(int i = 0; i < n; i++) {
push(1,i,0);
push(2,i,m-1);
}
int dy[4]{-1,0,1,0}, dx[4]{0,1,0,-1};
while(q.size()) {
auto [mask,y,x] = q.front(); q.pop();
for(int i = 0; i < 4; i++) {
int ny = y + dy[i], nx = x + dx[i];
if(0 <= ny and ny < n and 0 <= nx and nx < m and A[y][x] <= A[ny][nx]) push(mask,ny,nx);
}
}
int res = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(vis[i][j] == 3) res += 1;
}
}
return res;
}
|
