fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. const int M = 1e9 + 7;
  5.  
  6. //google sde-3 18th Sep
  7.  
  8. int main()
  9. {
  10. 	ios_base::sync_with_stdio(false);
  11. 	cin.tie(NULL);
  12. 	int n, m;
  13. 	cin >> n >> m;
  14. 	vector<vector<char>> v(n, vector<char>(m));
  15. 	vector<vector<int>> minfire_time(n, vector<int>(m, 1e9));
  16. 	queue<vector<int>> q;
  17. 	pair<int, int> s;
  18. 	for (int i = 0; i < n; i++)
  19. 	{
  20. 		for (int j = 0; j < m; j++)
  21. 		{
  22. 			cin >> v[i][j];
  23. 			if (v[i][j] == 'F')
  24. 			{
  25. 				q.push({i, j, 0});
  26. 				minfire_time[i][j] = 0;
  27. 			}
  28.  
  29. 			if (v[i][j] == 'S')
  30. 			{
  31. 				s.first = i;
  32. 				s.second = j;
  33. 			}
  34. 		}
  35. 	}
  36. 	vector<pair<int, int>> direc = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
  37.  
  38. 	while (!q.empty())
  39. 	{
  40. 		auto it = q.front();
  41. 		q.pop();
  42. 		int i = it[0];
  43. 		int j = it[1];
  44. 		int time = it[2];
  45. 		for (auto it : direc)
  46. 		{
  47. 			int x = i + it.first;
  48. 			int y = j + it.second;
  49.  
  50. 			if (x >= 0 && y >= 0 && x < n && y < m && v[x][y] != '#' && time + 1 < minfire_time[x][y])
  51. 			{
  52. 				minfire_time[x][y] = time + 1;
  53. 				q.push({x, y, minfire_time[x][y]});
  54. 			}
  55. 		}
  56. 	}
  57.  
  58. 	q.push({s.first, s.second, 0});
  59. 	int ans = -1;
  60. 	vector<vector<int>> vis(n, vector<int>(m, 0));
  61. 	vis[s.first][s.second] = 1;
  62. 	while (!q.empty())
  63. 	{
  64. 		auto it = q.front();
  65. 		q.pop();
  66. 		int i = it[0];
  67. 		int j = it[1];
  68. 		int time = it[2];
  69. 		if (v[i][j] == 'E')
  70. 		{
  71. 			ans = time;
  72. 			break;
  73. 		}
  74. 		for (auto it : direc)
  75. 		{
  76. 			int x = i + it.first;
  77. 			int y = j + it.second;
  78.  
  79. 			if (x >= 0 && y >= 0 && x < n && y < m && (v[x][y] == '.' || v[x][y] == 'E') && time + 1 < minfire_time[x][y] && vis[x][y] == 0)
  80. 			{
  81. 				vis[x][y] = 1;
  82. 				q.push({x, y, time + 1});
  83. 			}
  84. 		}
  85. 	}
  86.  
  87. 	cout << ans << endl;
  88.  
  89. 	return 0;
  90. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin 
5 6
S....E
.#.#..
F.#...
..#...
F.F...
stdout 
5
https://ideone.com/aPKyiQ
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!