fork download
copy 
  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <functional>
  4. #include <queue>
  5. #include <tuple>
  6. #include <vector>
  7. using namespace std;
  8. typedef vector<int> vi;
  9. int dx[4] = { 1,-1,0,0 };
  10. int dy[4] = { 0,0,1,-1 };
  11. queue<vi> Q;
  12. int D[26][26][26][26][26];
  13. char state[7][7];
  14. vi star(5,25);
  15. int starIdx = 0;
  16. int Dval(vi tmp) {
  17. 	return D[tmp[0]][tmp[1]][tmp[2]][tmp[3]][tmp[4]];
  18. }
  19. int* Dval_ptr(vi tmp) {
  20. 	return &D[tmp[0]][tmp[1]][tmp[2]][tmp[3]][tmp[4]];
  21. }
  22.  
  23. int isOutOfBounds(int x, int y) {
  24. 	return 0 > x || x >= 5 || 0 > y || y >= 5;
  25. }
  26. void conn_recursion(vector<int>& move, int idx, int dir) {
  27. 	int addX = move[idx] / 5;
  28. 	int addY = move[idx] % 5;
  29. 	int curX = addX + dx[dir];
  30. 	int curY = addY + dy[dir];
  31. 	if (isOutOfBounds(curX, curY) || find(move.begin(), move.end(), 5 * curX + curY) != move.end())
  32. 		return;
  33. 	if (move.size() == starIdx-1) {
  34. 		vector<int> tmp(5,25);
  35. 		int i = 0;
  36. 		for (; i < move.size(); i++)
  37. 			tmp[i] = move[i];
  38. 		tmp[i] = 5 * curX + curY;
  39. 		sort(tmp.begin(), tmp.end());
  40. 		if (Dval(tmp) == 0) {
  41. 			*Dval_ptr(tmp) = 1;
  42. 			Q.push(tmp);
  43. 		}
  44. 		return;
  45. 	}
  46. 	move.push_back(5 * curX + curY);
  47. 	for (int i = 0; i < move.size(); i++) {
  48. 		for (int dir = 0; dir < 4; dir++)
  49. 			conn_recursion(move, i, dir);
  50. 	}
  51. 	move.pop_back();
  52. }
  53. int main(void) {
  54. 	for (int i = 0; i < 5; i++)
  55. 		scanf("%s", state[i]);
  56. 	for (int i = 0; i < 5; i++)
  57. 		for (int j = 0; j < 5; j++)
  58. 			if(state[i][j] == '*') star[starIdx++] = 5 * i + j;
  59. 	if (starIdx == 1) {
  60. 		printf("0");
  61. 		return 0;
  62. 	}
  63. 	sort(star.begin(), star.end());
  64.  
  65. 	// 일단 연결된 애들부터 처리
  66. 	for (int x = 0; x < 5; x++) {
  67. 		for (int y = 0; y < 5; y++) {
  68. 			vector<int> move;
  69. 			move.push_back(5 * x+y);
  70. 			for(int dir = 0; dir < 4; dir++)
  71. 				conn_recursion(move,0,dir);
  72. 		}
  73. 	}
  74. 	while (!Q.empty()) {
  75. 		vi cur = Q.front();
  76. 		Q.pop();
  77. 		int val = Dval(cur);
  78. 		for (int idx = 0; idx < starIdx; idx++) {
  79. 			for (int dir = 0; dir < 4; dir++) {
  80. 				vi tmp = cur;
  81. 				int chX = tmp[idx] / 5 + dx[dir];
  82. 				int chY = tmp[idx] % 5 + dy[dir];
  83. 				if (isOutOfBounds(chX, chY) || find(tmp.begin(), tmp.end(), 5 * chX + chY) != tmp.end()) continue;
  84. 				tmp[idx] = 5 * chX + chY;
  85. 				sort(tmp.begin(), tmp.end());
  86. 				if (Dval(tmp) == 0) {
  87. 					*Dval_ptr(tmp) = val + 1;
  88. 					Q.push(tmp);
  89. 				}
  90. 			}
  91. 		}
  92. 	}
  93. 	printf("%d", Dval(star)-1);
  94. }
Success #stdin #stdout 0.08s 9024KB
comments (?)
stdin
copy 
*....
.....
.....
.....
**.**
stdout
copy 
5
https://ideone.com/QdOpLh
language:
C++14 (gcc 8.3)
created:
4 years 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!