fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define a first
  4. #define b second
  5.  
  6. using namespace std;
  7.  
  8. int X, Y, DP[1001][1001];
  9. bool GRAF[1001][1001], VIS[1001][1001];
  10. queue <pair <int, int>> Q;
  11.  
  12. void bfs(int x, int y) {
  13. 	Q.push({x, y});
  14. 	DP[x][y] = 0;
  15.  
  16. 	while (!Q.empty()) {
  17. 		x = Q.front().a;
  18. 		y = Q.front().b;
  19. 		Q.pop();
  20.  
  21. 		if (VIS[x][y])
  22. 			continue;
  23.  
  24. 		VIS[x][y] = 1;
  25.  
  26. 		if (x < X and !GRAF[x + 1][y])
  27. 			DP[x + 1][y] = min(DP[x + 1][y], DP[x][y]), Q.push({x + 1, y});
  28.  
  29. 		if (y > 1 and !GRAF[x][y - 1]) {
  30. 			DP[x][y - 1] = min(DP[x][y - 1], DP[x][y] + 1);
  31. 			if (!VIS[x][y - 1])
  32. 				Q.push({x, y - 1});
  33. 		} if (y < Y and !GRAF[x][y + 1]) {
  34. 			DP[x][y + 1] = min(DP[x][y + 1], DP[x][y] + 1);
  35. 			if (!VIS[x][y + 1])
  36. 				Q.push({x, y + 1});
  37. 		}
  38. 	}
  39. }
  40.  
  41. int main() {
  42. 	ios_base::sync_with_stdio(0);
  43. 	cin.tie(0); cout.tie(0);
  44.  
  45. 	cin >> Y >> X;
  46.  
  47. 	for (int y = 1; y <= Y; y ++)
  48. 		for (int x = 1; x <= X; x ++)
  49. 			cin >> GRAF[x][y];
  50.  
  51. 	const int INF = 1e6 + 1;
  52. 	int wy = INF;
  53.  
  54. 	for (int j = 1; j <= Y; j ++)
  55. 		for (int i = 1; i <= X; i ++)
  56. 			DP[i][j] = INF;
  57.  
  58. 	for (int y = 1; y <= Y; y ++) {
  59. 		if (!GRAF[1][y])
  60. 			bfs(1, y);
  61.  
  62. 		int mn = DP[X][1];
  63. 		for (int j = 2; j <= Y; j ++)
  64. 			mn = min(mn, DP[X][j]);
  65. 		wy = min(wy, mn);
  66.  
  67. 		for (int j = 1; j <= Y; j ++)
  68. 			for (int i = 1; i <= X; i ++)
  69. 				VIS[i][j] = 0;
  70. 	}
  71.  
  72. 	if (wy != INF)
  73. 		cout << wy;
  74. 	else
  75. 		cout << "NIE";
  76. }
Success #stdin #stdout 0.01s 5688KB
comments (?)
stdin
copy 
4 5
0 0 0 1 0
0 1 0 1 0
1 1 0 0 0
0 0 1 0 1
stdout
copy 
2
https://ideone.com/FPi6QR
pasyRuchu_30%
language:
C++14 (gcc 8.3)
created:
3 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!