fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define f first
  4. #define s second
  5. const int maxN = 1000;
  6. int grid[maxN][maxN];
  7. bool visited[maxN][maxN][2];
  8. int last[maxN][maxN];
  9. int dx[4] = {0, 0, -1, 1};
  10. int dy[4] = {1, -1, 0, 0};
  11. int dis[maxN][maxN]={};
  12. int n;
  13. bool valid(int x, int y, int l){
  14. 	return x >= 0 && x < n && y >= 0 && y < n && visited[x][y][l] == 0;
  15. }
  16. signed main(){
  17. 	cin >> n;
  18. 	for(int i = 0; i < n; i++)
  19. 		for(int j = 0; j < n; j++)
  20. 			cin >> grid[i][j];
  21.  
  22. 	queue<pair<int, int>> bfs;
  23. 	bfs.push({0, 0});
  24. 	dis[0][0] = 1;
  25. 	visited[0][0][0] = 1;
  26. 	visited[0][0][1] = 1;
  27. 	while(!bfs.empty()){
  28. 		int x = bfs.front().f;
  29. 		int y = bfs.front().s;
  30. 		bfs.pop();
  31. 		for(int i = 0; i < 4; i++){
  32. 			int nx = x + dx[i];
  33. 			int ny = y + dy[i];
  34. 			if(!x && !y){
  35. 				if(!valid(nx, ny, (grid[x][y] > grid[nx][ny]))) continue;
  36. 				visited[nx][ny][(grid[x][y] > grid[nx][ny])] = 1;
  37. 				last[nx][ny] = ((grid[x][y] > grid[nx][ny]) ? -1: 1);
  38. 				dis[nx][ny] = dis[x][y] + 1;
  39. 				bfs.push({nx, ny});
  40. 			}else{
  41. 				if(!valid(nx, ny, (grid[x][y] > grid[nx][ny])) || (grid[x][y] > grid[nx][ny]) == last[x][y]) continue;
  42. 				visited[nx][ny][(grid[x][y] > grid[nx][ny])] = 1 ;
  43. 				last[nx][ny] = (grid[x][y] > grid[nx][ny] ? -1: 1);
  44. 				dis[nx][ny] = dis[x][y] + 1;
  45. 				bfs.push({nx, ny});
  46. 			}
  47. 			for(int i = 0; i < n; i++){
  48. 			for(int j = 0; j < n; j++){
  49. 				cout << dis[i][j];
  50. 			}cout << endl;
  51. 			}cout << endl;
  52. 		}
  53.  
  54. 	}
  55. 	cout << visited[1][1][0];
  56. 		cout << (dis[n - 1][n - 1]? dis[n - 1][n - 1]: -1);
  57.  
  58. }
Success #stdin #stdout 0.01s 9640KB
comments (?)
stdin
copy 
3
15 16 18
13 11 9
2 7 3
stdout
copy 
120
000
000

120
200
000

123
200
000

123
230
000

123
230
300

123
234
300

123
434
300

123
434
340

123
434
340

123
454
340

123
454
345

123
456
345

15
https://ideone.com/3kGU9s
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

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!