67 lines
1.6 KiB
C++
67 lines
1.6 KiB
C++
// lanqiao 3820 混境之地
|
|
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
using ll = long long;
|
|
const ll p = 1e9 + 7;
|
|
const int inf = 1e9, N = 1e3 + 3;
|
|
|
|
int n, m, k, sx, sy, fx, fy, h[N][N];
|
|
int dx[] = {0, 0, 1, -1};
|
|
int dy[] = {1, -1, 0, 0};
|
|
|
|
int dp[N][N][2];
|
|
|
|
bool inmp(int x, int y){
|
|
return x >= 1 && x <= n && y >= 1 && y <= m;
|
|
}
|
|
// 返回值表示能否到达终点(fx, fy), t表示当前使用的喷气背包的次数
|
|
bool dfs(int x, int y, int t){
|
|
if(x == fx && y == fy) return true;
|
|
|
|
if(dp[x][y][t] != -1) return dp[x][y][t];
|
|
|
|
for(int i = 0; i < 4; i++){
|
|
int nx = x + dx[i], ny = y + dy[i];
|
|
if(!inmp(nx, ny)) continue;
|
|
if(!t){ // 没用过背包
|
|
// 不用
|
|
if(h[x][y] > h[nx][ny] && dfs(nx, ny, 0)) return dp[x][y][t] = true;
|
|
// 用
|
|
if(h[x][y] + k > h[nx][ny] && dfs(nx, ny, 1)) return dp[x][y][t] = true;
|
|
}else{ // 已经用过一次背包了
|
|
// 不用
|
|
if(h[x][y] > h[nx][ny] && dfs(nx, ny, 1)) return dp[x][y][t] = true;
|
|
}
|
|
}
|
|
return dp[x][y][t] = false;
|
|
}
|
|
int main(){
|
|
memset(dp, -1, sizeof dp); // 记忆化搜索
|
|
cin >> n >> m >> k;
|
|
cin >> sx >> sy >> fx >> fy;
|
|
for(int i = 1; i <= n; i++){
|
|
for(int j = 1; j <= m; j++){
|
|
cin >> h[i][j];
|
|
}
|
|
}
|
|
cout << (dfs(sx, sy, 0)?"Yes":"No") << '\n';
|
|
return 0;
|
|
}
|
|
/* test samples 1 -> YES
|
|
5 5 30
|
|
1 1 5 5
|
|
3 20 13 12 11
|
|
19 17 33 72 10
|
|
12 23 12 23 9
|
|
21 43 23 12 2
|
|
21 34 23 12 1
|
|
*/
|
|
/* test samples 1 -> NO
|
|
5 5 10
|
|
1 1 5 5
|
|
3 2 13 12 11
|
|
1 17 33 72 10
|
|
12 23 12 23 9
|
|
21 43 23 12 2
|
|
21 34 23 12 1
|
|
*/ |