fork(1) download
copy 
  1. //============================================================================
  2. // Name        : ACM.cpp
  3. // Author      : Tarango Khan
  4. // Copyright   : All Rights Reserved By Team Byteheads
  5. // Description : !!!Hello World!!!
  6. //============================================================================
  7.  
  8. #include <bits/stdc++.h>
  9. #include <stdio.h>
  10. #include <cstring>
  11. using namespace std;
  12. #define Pi 3.14159265359
  13. #define Max 9999999
  14. #define start_pos 15
  15.  
  16. int N;
  17.  
  18. char M[22][22];
  19. int row, col;
  20. int dx[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
  21. int dy[] = { 0, 0, 1, -1, -1, 1, 1, -1 };
  22. int food = 0, sx, sy;
  23.  
  24. int Set(int N, int pos) {
  25. 	return N = N | (1 << pos);
  26. }
  27. bool Check(int N, int pos) {
  28. 	return (bool) (N & (1 << pos));
  29. }
  30. map<int, pair<int, int> > Map;
  31. int total_nut = 0;
  32.  
  33. int isValid(int r, int c) {
  34. 	if (r < 0 || c < 0 || r >= row || c >= col){
  35. 		return 0;
  36. 	}
  37. 	return 1;
  38. }
  39.  
  40. struct point {
  41. 	int x;
  42. 	int y;
  43. 	int cnt;
  44. 	point(int a, int b, int c) {
  45. 		x = a;
  46. 		y = b;
  47. 		cnt = c;
  48. 	}
  49. };
  50.  
  51. int taken[22][22];
  52. int shortest_Path(int sR, int sC, int tR, int tC) {
  53. 	memset(taken, 0, sizeof(taken));
  54. 	queue<point> Q;
  55. 	Q.push(point(sR, sC, 0));
  56. 	taken[sR][sC] = 1;
  57.  
  58. 	while (Q.empty() == false) {
  59. 		point cur = Q.front();
  60. 		Q.pop();
  61. 		if (cur.x == tR && cur.y == tC) {
  62. 			return cur.cnt;
  63. 		}
  64. 		for (int i = 0; i < 8; i++) {
  65. 			int xx = cur.x + dx[i];
  66. 			int yy = cur.y + dy[i];
  67.  
  68. 			if (isValid(xx, yy) == 1 && taken[xx][yy] == 0) {
  69. 				taken[xx][yy] = 1;
  70. 				Q.push(point(xx, yy, cur.cnt + 1));
  71. 			}
  72. 		}
  73. 	}
  74. 	return 0;
  75. }
  76.  
  77. int distances[17][17];
  78.  
  79. void calculate_path() {
  80. 	for (int i = 0; i < total_nut; i++) {
  81. 		for (int j = 0; j < total_nut; j++) {
  82. 			distances[i][j] = distances[j][i] = shortest_Path(Map[i].first,
  83. 					Map[i].second, Map[j].first, Map[j].second);
  84. 		}
  85. 		distances[i][15] = distances[15][i] = shortest_Path(Map[i].first,Map[i].second, sx, sy);
  86. 	}
  87. }
  88.  
  89. int DP[70000][17];
  90.  
  91. int call(int mask, int r, int c, int pos) {
  92. 	//printf("Currently at row: %d , col: %d mask: %d\n",r,c,mask);
  93. 	if (mask == (1 << total_nut) - 1) {
  94. 		int ed = distances[pos][start_pos];
  95. 		//printf("\nEnded at r: %d , c: %d for %d\n\n",r,c,ed);
  96. 		return DP[mask][pos] = ed;
  97. 	}
  98. 	if (pos != start_pos){
  99. 		if (DP[mask][pos] != -1) {
  100. 			return DP[mask][pos];
  101. 		}
  102. 	}
  103. 	int dist = Max;
  104. 	//One by one trying to select next # to take
  105. 	for (int i = 0; i < total_nut; i++) {
  106. 		if (Check(mask, i) == 0) {
  107. 			//printf("Taking hash: %d where r: %d , c: %d\n",i,Map[i].first,Map[i].second);
  108. 			int total_cost = call(Set(mask, i), Map[i].first, Map[i].second, i)	+ distances[pos][i];
  109. 			//printf("...At this step, res: %d...\n",total_cost);
  110. 			dist = min(dist, total_cost);
  111. 		}
  112. 	}
  113. 	//printf("\nFinally at row: %d , col: %d mask: %d , cost: %d\n\n",r,c,mask,dist);
  114. 	if (dist != Max && pos != start_pos) {
  115. 		return DP[mask][pos] = dist;
  116. 	}
  117. 	return dist;
  118. }
  119.  
  120. int main() {
  121. 	while (scanf("%d %d", &row, &col) == 2) {
  122. 		total_nut = 0;
  123. 		getchar();
  124. 		for(int i = 0;i<row;i++){
  125. 			gets(M[i]);
  126. 		}
  127. 		for (int i = 0; i < row; i++) {
  128. 			for (int j = 0; j < col; j++) {
  129. 				if (M[i][j] == 'L') {
  130. 					sx = i;
  131. 					sy = j;
  132. 				}
  133. 				//Saving in Map where we find #
  134. 				if (M[i][j] == '#') {
  135. 					pair<int, int> P;
  136. 					P.first = i;
  137. 					P.second = j;
  138. 					Map[total_nut] = P;
  139. 					total_nut++;
  140. 				}
  141. 			}
  142. 		}
  143. 		calculate_path();
  144. 		memset(DP, -1, sizeof(DP));
  145. 		int res = call(0, sx, sy, start_pos);
  146. 		printf("%d\n", res);
  147. 	}
  148. 	return 0;
  149. }
  150.  
Compilation error #stdin compilation error #stdout 0s 7936KB
comments (?)
stdin
copy 
5 5
L....
#....
#....
.....
#....
5 5
L....
#....
#....
.....
#....
compilation info 
prog.cpp: In function 'int main()':
prog.cpp:125:13: error: 'gets' was not declared in this scope
    gets(M[i]);
             ^
stdout
copy 
Standard output is empty
https://ideone.com/xVl0JI
language:
C++14 (gcc 8.3)
created:
8 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!