fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. // zamiast pisac first, second pisze a, b
  4.  
  5. #define a first
  6. #define b second
  7.  
  8. using namespace std;
  9.  
  10. // X - dlugosc pasa, Y - ilosc pasow, DP[x][y] - najmniejsza
  11. // liczba skretow aby dostac sie na miejsce GRAF[x][y]
  12.  
  13. // GRAF[x][y] - informacje o autostradzie, VIS[x][y] - odwiedzony
  14.  
  15. // Q - kolejka przydatna do bfs'a
  16.  
  17. // ODW - ktore indeksy odwiedzalem - przyda sie
  18. // w optymalizacji zerowania tablicy VIS
  19.  
  20. int X, Y, DP[1001][1001]; 
  21. bool GRAF[1001][1001], VIS[1001][1001];
  22. queue <pair <int, int>> Q;
  23. vector <pair <int, int>> ODW;
  24.  
  25. void bfs(int x, int y) {
  26. 	Q.push({x, y});
  27. 	DP[x][y] = 0;
  28.  
  29. 	while (!Q.empty()) {
  30. 		x = Q.front().a;
  31. 		y = Q.front().b;
  32. 		Q.pop();
  33.  
  34. 		if (VIS[x][y])
  35. 			continue;
  36.  
  37. 		VIS[x][y] = 1;
  38. 		ODW.push_back({x, y});
  39.  
  40. 		if (x < X and !GRAF[x + 1][y])
  41. 			DP[x + 1][y] = min(DP[x + 1][y], DP[x][y]), Q.push({x + 1, y});
  42.  
  43. 		if (y > 1 and !GRAF[x][y - 1]) {
  44. 			DP[x][y - 1] = min(DP[x][y - 1], DP[x][y] + 1);
  45. 			if (!VIS[x][y - 1])
  46. 				Q.push({x, y - 1});
  47. 		} if (y < Y and !GRAF[x][y + 1]) {
  48. 			DP[x][y + 1] = min(DP[x][y + 1], DP[x][y] + 1);
  49. 			if (!VIS[x][y + 1])
  50. 				Q.push({x, y + 1});
  51. 		}
  52. 	}
  53. }
  54.  
  55. int main() {
  56. 	ios_base::sync_with_stdio(0);
  57. 	cin.tie(0); cout.tie(0);
  58.  
  59. 	cin >> Y >> X;
  60.  
  61. 	for (int y = 1; y <= Y; y ++)
  62. 		for (int x = 1; x <= X; x ++)
  63. 			cin >> GRAF[x][y];
  64.  
  65.  
  66. 	// na poczatku ustawiam max wartosc na kazdym elemencie
  67. 	const int INF = 1e6 + 1;
  68. 	int wy = INF;
  69.  
  70. 	for (int j = 1; j <= Y; j ++)
  71. 		for (int i = 1; i <= X; i ++)
  72. 			DP[i][j] = INF;
  73.  
  74. 	for (int y = 1; y <= Y; y ++) {
  75. 		if (!GRAF[1][y])
  76. 			bfs(1, y);
  77.  
  78. 		// szukam min wsrod zakonczen autostrady
  79. 		int mn = DP[X][1];
  80. 		for (int j = 2; j <= Y; j ++)
  81. 			mn = min(mn, DP[X][j]);
  82. 		wy = min(wy, mn);
  83.  
  84. 		// zeruje odwiedzone elementy w tablicy VIS
  85. 		for (auto a : ODW)
  86. 			VIS[a.a][a.b] = 0;
  87. 		ODW.clear();
  88. 	}
  89.  
  90. 	if (wy != INF)
  91. 		cout << wy;
  92. 	else
  93. 		cout << "NIE";
  94. }
Success #stdin #stdout 0.01s 5632KB
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/gkTgf3
pasyRuchuOpt_90%
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!