fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int X, Y, DP[1001][1001]; 
  6. bool GRAF[1001][1001];
  7.  
  8. int main() {
  9. 	ios_base::sync_with_stdio(0);
  10. 	cin.tie(0); cout.tie(0);
  11.  
  12. 	cin >> Y >> X;
  13.  
  14. 	for (int y = 1; y <= Y; y ++)
  15. 		for (int x = 1; x <= X; x ++)
  16. 			cin >> GRAF[x][y];
  17.  
  18. 	const unsigned int INF = 1e6 + 1;
  19. 	for (int y = 1; y <= Y; y ++)
  20. 		for (int x = 1; x <= X; x ++)
  21. 			DP[x][y] = INF;
  22.  
  23. 	for (int x = 1; x <= X; x ++) {
  24. 		for (int y = 1; y <= Y; y ++) {
  25. 			if (!GRAF[x][y] and !GRAF[x - 1][y])
  26. 				DP[x][y] = DP[x - 1][y];
  27. 		}
  28.  
  29. 		for (int y = 1; y <= Y; y ++) {
  30. 			if (!GRAF[x][y]) {
  31. 				if (y > 1)
  32. 					DP[x][y] = min(DP[x][y], DP[x][y - 1] + 1);
  33.  
  34. 				DP[x][y] = min(DP[x][y], DP[x - 1][y]);
  35.  
  36. 				if (y < Y)
  37. 					DP[x][y] = min(DP[x][y], DP[x][y + 1] + 1);
  38. 			}
  39. 		}
  40. 	}
  41.  
  42. 	int mn = DP[X][1];
  43. 	for (int y = 2; y <= Y; y ++)
  44. 		mn = min(mn, DP[X][y]);
  45.  
  46. 	if (mn != INF)
  47. 		cout << mn;
  48. 	else
  49. 		cout << "NIE";
  50. }
Success #stdin #stdout 0.01s 5416KB
comments (?)
stdin 
4 5
0 0 0 1 0
0 1 0 1 0
1 1 0 0 0
0 0 1 0 1
stdout 
2
https://ideone.com/Hzlox8
pasyRuchu
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!