#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned int ui; const ll mod = 1000000007; const ll INF = (ll)1000000007 * 1000000007; typedef pair P; #define stop char nyaa;cin>>nyaa; #define rep(i,n) for(int i=0;i=0;i--) #define Rep(i,sta,n) for(int i=sta;i=sta;i--) #define rep1(i,n) for(int i=1;i<=n;i++) #define per1(i,n) for(int i=n;i>=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) typedef long double ld; typedef complex Point; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair LP; int n,v,ox,oy; int l[210][210]; vector> G; template vector dijkstra(int s,vector>> & G){ const T inf=numeric_limits::max(); using edge=pair; priority_queue, greater > que; int n=G.size(); vector d(n,inf); vector b(n,-1); d[s]=0; que.emplace(d[s],s); while (!que.empty()){ edge p = que.top(); que.pop(); //cout << p.first << endl; int v = p.second; if (d[v]d[v]+c){ d[u]=d[v]+c; b[u]=v; que.emplace(d[u],u); } } } return d; } void solve(){ cin >> n >> v >> ox >> oy; ox--;oy--; G.resize(n*n,{}); rep(i,n){ rep(j,n){ cin >> l[i][j]; } } rep(i,n){ rep(j,n){ if (i>=1) G[(i-1)*n+j].push_back(P(l[i][j],i*n+j)); if (i<=n-2) G[(i+1)*n+j].push_back(P(l[i][j],i*n+j)); if (j>=1) G[i*n+j-1].push_back(P(l[i][j],i*n+j)); if (j<=n-2) G[i*n+j+1].push_back(P(l[i][j],i*n+j)); } } vector d1=dijkstra(0,G); int ans=0; ans=d1[n*(n-1)+n-1]; //cout << ans << endl; if (ans d2=dijkstra(oy*n+ox,G); ans=d1[ox*n+oy]; if (ans>=v) { cout << "NO" << endl; return; } v=2*(v-ans); ans=d2[n*(n-1)+n-1]; if (ans