// 想定解法: 格子点平面上の最短経路探索(Dijkstra, SPFA, etc.) // これはSPFA // オアシスを通らずに体力値未満のコストで到達できるなら YES // スタート→オアシス→ゴール経路で体力値未満のコストで到達できるなら YES // それ以外ならNO #include #include #include using namespace std; #define REP(i, n) for(int(i)=0;(i)<(n);++(i)) const int MAXN = 200; int board[MAXN][MAXN]; int cost[MAXN][MAXN]; const int INF = 1<<29; int N, V, OX, OY; const int dir[][2] = {{1,0},{0,1},{-1,0},{0,-1}}; void solve(int sx, int sy){ bool inq[MAXN][MAXN]; REP(y,N) REP(x,N){ cost[y][x] = INF; inq[y][x] = false; } deque > q; q.push_back(make_pair(sx,sy)); cost[sy][sx] = 0; inq[sy][sx] = true; while(!q.empty()){ int x = q.front().first, y = q.front().second; q.pop_front(); int nowcost = cost[y][x]; inq[y][x] = false; for(int d = 0; d < 4; d++){ int mx = x + dir[d][0]; int my = y + dir[d][1]; if(mx < 0 || my < 0 || mx >= N || my >= N) continue; int nextcost = nowcost + board[my][mx]; if(cost[my][mx] > nextcost){ cost[my][mx] = nextcost; if(!inq[my][mx]){ q.push_back(make_pair(mx,my)); inq[my][mx] = true; } } } } return; } int main(){ cin >> N >> V >> OX >> OY; REP(y,N) REP(x,N) cin >> board[y][x]; solve(0,0); // 直接目的地に行けるか? if(cost[N-1][N-1] < V){ cout << "YES" << endl; return 0; } if(OX && OY){ int oc = cost[OY-1][OX-1]; // オアシスに行けるか? if(oc < V){ solve(OX-1,OY-1); // オアシスから目的地に行けるか? if(cost[N-1][N-1] < (V-oc)*2){ cout << "YES" << endl; return 0; } } } cout << "NO" << endl; return 0; }