fork download
copy 
  1. #include <iostream>
  2. #include <queue>
  3.  
  4. using namespace std;
  5. using pii = pair<int, int>;
  6. using pii_pii = pair<pii, pii>;
  7.  
  8. int dr[] = {-1, 0, 1, 0};
  9. int dc[] = {0, 1, 0, -1};
  10.  
  11. int bfs(vector<string>& board, pii& src, pii& dst1, pii& dst2){
  12.  
  13. 	bool visited[51][51][5][4];
  14. 	visited[src.first][src.second][4][0] = true;
  15.  
  16. 	queue<pair<pii_pii, int>> q;
  17. 	q.push(make_pair(make_pair(make_pair(-1, 0), src), 0));
  18.  
  19. 	while(!q.empty()){
  20.  
  21. 		int dir = q.front().first.first.first;
  22. 		int cnt = q.front().first.first.second;
  23. 		auto now = q.front().first.second;
  24. 		int bit = q.front().second;
  25. 		q.pop();
  26.  
  27. 		if(bit == 3){
  28. 			return cnt;
  29. 		}
  30.  
  31. 		for(int i = 0; i < 4; i++){
  32. 			int next_r = now.first + dr[i];
  33. 			int next_c = now.second + dc[i];
  34. 			auto next = make_pair(next_r, next_c);
  35. 			int next_bit = bit | (next == dst1) | (2 * (next == dst2));
  36. 			if(next_r < 0 or next_r >= board.size() or next_c < 0 or next_c >= board[0].size() or dir == i){
  37. 				continue;
  38. 			}
  39. 			if(!visited[next_r][next_c][i][next_bit] and board[next_r][next_c] != '#'){
  40. 				visited[next_r][next_c][i][next_bit] = true;
  41. 				q.push(make_pair(make_pair(make_pair(i, cnt + 1), next), next_bit));
  42. 			}
  43. 		}
  44. 	}
  45.  
  46. 	return -1;
  47. }
  48.  
  49. int main() {
  50.  
  51. 	ios_base::sync_with_stdio(0);
  52. 	cin.tie(0);
  53.  
  54. 	int R, C;
  55. 	cin >> R >> C;
  56.  
  57. 	vector<string> board(R);
  58.  
  59. 	pii src, dst[2];
  60. 	int cnt = 0;
  61.  
  62. 	for(int i = 0; i < R; i++){
  63. 		cin >> board[i];
  64. 		for(int j = 0; j < C; j++){
  65. 			if(board[i][j] == 'S'){
  66. 				src.first = i;
  67. 				src.second = j;
  68. 			}else if(board[i][j] == 'C'){
  69. 				dst[cnt].first = i;
  70. 				dst[cnt++].second = j;
  71. 			}
  72. 		}
  73. 	}
  74. 	cout << bfs(board, src, dst[0], dst[1]);
  75.  
  76. 	return 0;
  77. }
Success #stdin #stdout 0.01s 5360KB
comments (?)
stdin
copy 
3 36
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#C
.................S..................
C#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
stdout
copy 
155
https://ideone.com/ucFGCB
language:
C++ (gcc 8.3)
created:
1 year 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!