fork(1) download
  1. #include<bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. using namespace std;
  5. int T[501][501];
  6. bool odw[501][501];
  7. int n,w;
  8.  
  9. void dfs(int x,int y,int kary){
  10. odw[x][y]=1;
  11. if(0<=x-1&&odw[x-1][y]==0){
  12. if(T[x-1][y]<w) dfs(x-1,y,kary);
  13. else if(kary>0) dfs(x-1,y,kary-1);
  14. }
  15. if(x+1<n&&odw[x+1][y]==0){
  16. if(T[x+1][y]<w) dfs(x+1,y,kary);
  17. else if(kary>0) dfs(x+1,y,kary-1);
  18. }
  19. if(0<=y-1&&odw[x][y-1]==0){
  20. if(T[x][y-1]<w) dfs(x,y-1,kary);
  21. else if(kary>0) dfs(x,y-1,kary-1);
  22. }
  23. if(y+1<n&&odw[x][y+1]==0){
  24. if(T[x][y+1]<w) dfs(x,y+1,kary);
  25. else if(kary>0) dfs(x,y+1,kary-1);
  26. }
  27. }
  28.  
  29. int main(){
  30. ios_base::sync_with_stdio(0);
  31. cin.tie(0);
  32. int a,b,c,d,kary;
  33. int p=-1,k=0,sr;
  34. cin>>n>>kary>>a>>b>>c>>d;
  35. a--; b--; c--; d--;
  36. if(abs(a-c)+abs(b-d)<kary){
  37. cout<<"TRIV";
  38. return 0;
  39. }
  40. for(int i=0;i<n;i++){
  41. for(int j=0;j<n;j++){
  42. cin>>T[i][j];
  43. if(k<T[i][j]) k=T[i][j];
  44. }
  45. }
  46. if(a==c&&b==d){
  47. cout<<T[a][b];
  48. return 0;
  49. }
  50. k++;
  51. while(k-p>1){
  52. w=(p+k)/2;
  53. for(int i=0;i<n;i++) for(int j=0;j<n;j++) odw[i][j]=0;
  54. if(T[a][b]>=w) dfs(a,b,kary-1);
  55. else dfs(a,b,kary);
  56. if(odw[c][d]==1) k=w;
  57. else p=w;
  58. }
  59. cout<<p;
  60. }
Success #stdin #stdout 0.01s 5268KB
stdin
2 0
1 2 2 1
2 1
3 7
stdout
3