Problem Statement
There is a grid with $H$ horizontal rows and $W$ vertical columns. Let $(i, j)$ denote the cell at the $i$-th row $(1\leq i\leq H)$ from the top and $j$-th column $(1\leq j\leq W)$ from the left.
Initially, there is a slime with strength $S _ {i,j}$ in cell $(i,j)$, and Takahashi is the slime in the cell $(P,Q)$.
Find the maximum possible strength of Takahashi after performing the following action any number of times (possibly zero):
- Among the slimes adjacent to him, choose one whose strength is strictly less than $\dfrac{1}{X}$ times his strength and absorb it. As a result, the absorbed slime disappears, and Takahashi’s strength increases by the strength of the absorbed slime.
When performing the above action, the gap left by the disappeared slime is immediately filled by Takahashi, and the slimes that were adjacent to the disappeared one (if any) become newly adjacent to Takahashi (refer to the explanation in sample 1).
Constraints
- $1\leq H,W\leq500$
- $1\leq P\leq H$
- $1\leq Q\leq W$
- $1\leq X\leq10^9$
- $1\leq S _ {i,j}\leq10^{12}$
- All input values are integers.
The input is given in the following format from Standard Input:
$H$ $W$ $X$
$P$ $Q$
$S _ {1,1}$ $S _ {1,2}$ $\ldots$ $S _ {1,W}$
$S _ {2,1}$ $S _ {2,2}$ $\ldots$ $S _ {2,W}$
$\vdots$
$S _ {H,1}$ $S _ {H,2}$ $\ldots$ $S _ {H,W}$
Output
Print the maximum possible strength of Takahashi after performing the action.
Solving
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n,m,x,sx,sy;
const int N = 505;
ll mp[N][N];
bool vis[N][N] = {false};
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
//<sth,[x,y]>
typedef pair<ll,pair<ll,ll>> pll;
bool check(int x,int y)//check if the coord legal
{
if(x<=0||y<=0||x>n||y>m) return false;
if(vis[x][y]) return false;
return true;
}
ll nxt_pow(ll pow)//return the power after devoured another block,if its greater than the top element in the minheap is legal
{
if(pow%x==0) return pow/x-1;
else return pow/x;
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin >> n >> m >> x;
cin >> sx >> sy;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin >> mp[i][j];
}
}
// strength and [x,y]
priority_queue<pll,vector<pll>,greater<pll>> q;//build Min-Heap
q.push({mp[sx][sy],{sx,sy}});//push the start into heap
vis[sx][sy] = true;
ll power = 0;//start with zero cuz in step one power will automatically add sth[sx,sy]
bool start = true;
//start BFS
while(!q.empty()&&nxt_pow(power) >= q.top().first||start)
{
start = false;
int now_x = q.top().second.first;
int now_y = q.top().second.second;
ll now_power = q.top().first;
power += now_power;
q.pop();
for(int i=0;i<4;i++)
{
int nx = now_x + dx[i];
int ny = now_y + dy[i];
if(check(nx,ny))
{
q.push({mp[nx][ny],{nx,ny}});
vis[nx][ny] = true;
}
}
}
//output the ans
cout << power;
return 0;
}
|