fork download
copy 
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <set>
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. const int INF = 1000000000;
  9.  
  10. int N, M;
  11. int A[100];
  12. int g[100][100];
  13. int a, b, c;
  14. int count_city = 0;
  15. int dp[1024][10];
  16. int dist(int a, int b) {
  17. 	return max(abs(g[a][0] - g[b][0]), abs(g[a][1] - g[b][1]));
  18. }
  19. int main() {
  20.  
  21.     cin >> N >> M;
  22.    for (int i = 0; i < N; i++) {
  23. 		for (int j = 0; j < M; j++) {
  24. 			scanf("%c", &c);
  25. 			if (c == 'L' || c == '#'){ 
  26. 				g[count_city][0] = i;
  27. 				g[count_city][1] = j;
  28. 				count_city++;
  29. 			}
  30. 		}
  31. 		scanf("%c", &c);
  32. 	}
  33.  
  34.     for (int i = 0; i < (1<<N); i++) {
  35.         for (int j = 0; j < N; j++) {
  36.             dp[i][j] = INF;
  37.         }
  38.     }
  39.  
  40.     dp[0][0] = 0;
  41.     for (int mask = 0; mask < (1<<N); mask++) {
  42.         for (int i = 0; i < N; i++) {
  43.             if (dp[mask][i] == INF) continue;
  44.             for (int j = 0; j < N; j++) {
  45.                 if ((mask & (1 << j)) == 0) {
  46.                     dp[mask | (1<<j)][j] = min(dp[mask | (1<<j)][j], dp[mask][i] + g[i][j]);
  47.                 }
  48.             }
  49.         }
  50.         /*for (int i = 0; i < N; i++) {
  51.             cout << dp[mask][i] << ' ';
  52.         }
  53.         cout << endl;*/
  54.     }
  55.     cout << dp[(1<<N)-1][0] << endl;
  56.      int answ;   
  57. int mask = (1 << count_city) - 1;
  58. 	for (int i = 0; i < count_city; i++) {
  59. 		answ = min(answ, dp[mask][i] + dist(i, 0));
  60. 	}
  61. 	printf("%d", answ);
  62.  
  63.     return 0;
  64. }
  65.  
Success #stdin #stdout 0s 5444KB
comments (?)
stdin
copy 
5 5
L....
#....
#....
.....
#....
stdout
copy 
1
0
https://ideone.com/bB46yH
language:
C++ (gcc 8.3)
created:
2 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!