fork(1) download
copy 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <string>
  9. #include <queue>
  10. #include <stack>
  11. #include <algorithm>
  12. #include <iomanip>
  13. #define dibs reserve
  14. #define OVER9000 1234567890
  15. #define patkan 9
  16. #define tisic 47
  17. #define soclose 10e-7
  18. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  19. #define chocolate win
  20. #define ff first
  21. #define ss second
  22. #define abs(x) ((x < 0)?-(x):(x))
  23. // mylittlepony
  24. using namespace std;
  25.  
  26. int main() {
  27.     cin.sync_with_stdio(0);
  28.     int N;
  29.     cin >> N;
  30.     N =2*N+1;
  31.     vector< vector<int> > val(N,vector<int>(N));
  32.     for(int i =0; i < N; i++) for(int j =0; j < N; j++) cin >> val[i][j];
  33.  
  34.     queue< pair<int,int> > q;
  35.     q.push(make_pair((N/2)*5+4,N/2));
  36.     int dx[] ={0,0,1,-1};
  37.     int dy[] ={1,-1,0,0};
  38.     vector< vector<int> > D[5];
  39.     for(int i =0; i < 5; i++) D[i].resize(N,vector<int>(N,N*N+tisic));
  40.     D[4][N/2][N/2] =0;
  41.  
  42.     while(!q.empty()) {
  43.     	pair<int,int> p =q.front();
  44.     	int x =p.ff/5, y =p.ss, t =p.ff%5;
  45.     	int d =(t == 4)?OVER9000:(val[x-dx[t]][y-dy[t]]-val[x][y]);
  46.     	for(int k =0; k < 4; k++) if(min(x+dx[k],y+dy[k]) >= 0 && max(x+dx[k],y+dy[k]) < N) {
  47.     		if(d >= val[x][y]-val[x+dx[k]][y+dy[k]] && val[x][y]-val[x+dx[k]][y+dy[k]] >= 0 && D[k][x+dx[k]][y+dy[k]] > D[t][x][y]+1) {
  48.     			D[k][x+dx[k]][y+dy[k]] =D[t][x][y]+1;
  49.     			q.push(make_pair(5*(x+dx[k])+k,y+dy[k]));}
  50.     		}
  51.     	q.pop();}
  52.  
  53.     int d =N*N+tisic;
  54.     for(int i =0; i < N; i++) for(int j =0; j < N; j++) for(int k =0; k < 5; k++)
  55.     	if(i == 0 || j == 0 || i == N-1 || j == N-1) d =min(d,D[k][i][j]);
  56.     if(d > N*N) {cout << "IMPOSSIBLE\n"; return 0;}
  57. 	cout << d << "\n";
  58.     for(int i =0; i < N; i++) for(int j =0; j < N; j++) for(int k =0; k < 5; k++) 
  59.     	if(i == 0 || j == 0 || i == N-1 || j == N-1) if(D[k][i][j] == d) {
  60.     		cout << i+1 << " " << j+1 << "\n";
  61.     		return 0;}
  62.    	return 0;}
  63.  
  64. // look at my code
  65. // my code is amazing
Success #stdin #stdout 0s 3488KB
comments (?)
stdin
copy 
2
3 1 2 4 5
1 3 4 5 4
2 4 5 4 2
4 5 4 3 1
5 4 2 1 3
stdout
copy 
IMPOSSIBLE
https://ideone.com/zWhqbn
CT S02E04 C
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!