#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define INF_MIN 100000000 #define INF 1145141919 #define INF_MAX 2147483647 #define LL_MAX 9223372036854775807 #define EPS 1e-10 #define PI acos(-1) #define LL long long using namespace std; #define MAX_N 201 #define MAX_V 1010 typedef pair P; int N, V, Ox, Oy; int L[MAX_N][MAX_N]; int maze[MAX_N][MAX_N]; int dp[MAX_N][MAX_N][MAX_V][2]; int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1}; string solve(){ dp[0][0][V][0] = 0; queue

que; queue

Vque; que.push(P(0, 0)); Vque.push(P(V, 0)); while(que.size()){ P p = que.front(); P v = Vque.front(); que.pop(); Vque.pop(); int x = p.first, y = p.second; int hp = v.first, flag = v.second; if(x == N-1 && y == N-1) return "YES"; for(int d = 0; d < 4; d++){ int nx = x + dx[d]; int ny = y + dy[d]; if(0 <= nx && nx < N && 0 <= ny && ny < N){ int nextHp = hp - maze[ny][nx]; if(nextHp <= 0) continue; if(nx == Ox && ny == Oy && flag == 0){ if(dp[ny][nx][nextHp*2][1] > dp[y][x][hp][0] + 1){ dp[ny][nx][nextHp*2][1] = dp[y][x][hp][0] + 1; que.push(P(nx, ny)); Vque.push(P(nextHp*2, 1)); } } else{ if(dp[ny][nx][nextHp][flag] > dp[y][x][hp][flag] + 1){ dp[ny][nx][nextHp][flag] = dp[y][x][hp][flag] + 1; que.push(P(nx, ny)); Vque.push(P(nextHp, flag)); } } } } } return "NO"; } int main(){ cin >> N >> V >> Ox >> Oy; Ox--; Oy--; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ cin >> maze[i][j]; for(int k = 0; k < MAX_V; k++){ dp[i][j][k][0] = dp[i][j][k][1] = INF; } } } cout << solve() << endl; return 0; }