fork(1) download
  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
stdin
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
Standard output is empty