fork download
  1. #include<bits/stdc++.h>
  2. #define endl "\n"
  3. using namespace std;
  4. typedef long long ll;
  5. typedef unsigned long long ull;
  6. const int N = 1e5;
  7. const int MOD = 1000000007;
  8. int row, col;
  9. vector<pair<int, int>>v;
  10. int n;
  11. int dp[25][1 << 21];
  12. int solve(int mask, int idx, pair<int, int>prev)
  13. {
  14. if(idx == n) return 0;
  15. if(mask == (1 << n) - 1) return 0;
  16. if(dp[idx][mask] != -1) return dp[idx][mask];
  17. int res = 1e9;
  18. for(int i=0; i<n; i++)
  19. {
  20. if((mask & (1 << i)) == false)
  21. {
  22. pair<int, int>curr = v[i];
  23. int dis = max(abs(curr.first-prev.first), abs(curr.second-prev.second));
  24. res = min(res, dis + solve((mask | (1 << i)), idx + 1, curr));
  25. }
  26. }
  27. return dp[idx][mask] = res;
  28. }
  29. int main()
  30. {
  31. //ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
  32.  
  33. //freopen("inputs.txt", "r", stdin);
  34. //freopen("output.txt", "w", stdout);
  35.  
  36. int t, cases = 1;
  37. cin >> t;
  38. while(t--)
  39. {
  40. cin >> row >> col;
  41. v.clear();
  42. pair<int, int>start;
  43. for(int i=0; i<row; i++)
  44. {
  45. for(int j=0; j<col; j++)
  46. {
  47. char ch;
  48. cin >> ch;
  49. if(ch == 'x') start.first = i + 1, start.second = j + 1;
  50. else if(ch == 'g') v.push_back({i+1, j+1});
  51. }
  52. }
  53. n = v.size();
  54. memset(dp, -1, sizeof(dp));
  55. cout << "Case " << cases++ << ": " << solve(0, 0, start) * 2 << endl;
  56. }
  57.  
  58.  
  59. }
  60.  
Success #stdin #stdout 1.33s 208324KB
stdin
100
11 3
...
gg.
...
.xg
...
g..
...
...
.g.
...
...
13 13
...g.........
.............
.............
.............
.g...........
....g........
.............
.......g.....
....gg.x.....
.............
...........gg
.....g.....g.
.gg..........
6 4
g...
.ggx
...g
g...
g.g.
.ggg
8 15
...............
...............
.............g.
...g...........
..x...........g
...............
...............
.g.............
5 14
..............
..............
g..g........x.
..............
...........g..
15 18
..................
..................
..................
..................
..................
..................
..................
..................
..........x.......
..................
..g...............
..................
..................
..................
..................
3 5
.g...
....g
.gg.x
10 17
.................
..........x......
.................
.................
.................
.................
.................
.................
..g..............
.........g.......
11 8
........
........
........
......g.
........
........
........
........
........
......x.
.g....g.
16 14
..............
.......g......
..............
.........g....
..............
...g....g....g
..............
........x.....
g..........g..
..............
..........g...
..............
..............
..g...........
.........g....
...g.gg.......
19 3
...
..g
...
..g
...
...
...
..g
...
x..
...
...
...
g..
...
.g.
g..
g..
...
3 13
........g...x
.....g...g...
g....gg...gg.
2 18
...............g.g
....g..x.g........
12 1
.
g
g
g
.
.
g
x
.
g
.
g
5 12
......g.....
............
............
....gg.....g
.g......g.x.
13 8
........
........
.....g..
........
........
g.g.....
g.......
........
........
....g...
.....g..
........
..x.g...
1 2
x.
7 4
....
x...
.g..
....
....
g..g
gg..
2 20
.gg...g.g...........
ggg.g..x..g.gg...g..
1 17
..x.....g........
15 1
g
g
g
g
g
g
g
g
g
g
g
.
g
g
x
1 11
gg.gg.g..xg
2 20
x...................
..g.................
16 19
..........g..x.....
..............g....
....g..............
.............g.....
...................
...................
.........g.........
...................
.......g...........
.g.............g...
....g.......g......
......g............
...g...............
...................
...................
.......g...........
8 12
..g....g..g.
..gg...g....
............
............
..g.g....g..
............
....g...g...
..x.g....g..
18 4
....
g...
.x..
.g..
....
....
..g.
....
....
....
...g
.g..
....
....
....
...g
....
.g..
5 1
g
g
.
x
g
19 18
..................
..................
............g.....
..................
........x.........
......g.........g.
..................
..................
.........g........
............gg....
.....g............
..................
..................
..................
..........g.......
..................
..g...............
..............g...
........g......g..
12 17
.................
.................
...............g.
.................
.................
......g.g........
.....g...........
....g........g...
...............g.
..........g....x.
.................
.................
6 16
.............x..
................
................
...g............
................
................
17 12
............
..........g.
............
............
............
.g..........
............
..g.........
............
............
............
...x.g......
g...........
............
............
............
............
13 7
.......
.....g.
..g...g
.g.....
.x.....
....g..
.g....g
.g.....
.......
g...gg.
......g
.......
.......
2 4
xg.g
g.gg
17 6
...g..
.g.g.g
......
......
..g...
.g.g..
......
......
....g.
......
......
g.....
....g.
....g.
......
...ggx
..gg..
4 11
.......g...
.g...ggg..g
..........g
..g....g.x.
5 13
....g.....ggg
.g.g.g..g.xg.
.g....gg.....
......g.g..g.
.............
14 7
.......
.......
.g.....
.......
.......
.......
......x
..g....
.......
....g..
.......
.......
....g..
..g....
16 19
...................
..................x
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
...................
3 1
.
g
x
8 5
g...g
..ggg
..gxg
.....
..g..
g..g.
.g.gg
g...g
14 19
...................
.....g.....g...g...
..........g......g.
...................
...................
...g...............
...................
...................
...g...........g...
.....g...g.........
..g.......g........
...................
g.......g..........
....xg.............
19 7
g......
.g.....
.....g.
gg.....
...g...
.......
.......
.......
......g
....g..
.....g.
g.g....
.......
.......
.......
...x...
.......
.....g.
.......
16 18
..................
.......g..........
..................
..............g...
..................
..................
..................
..................
........g.........
.g................
..................
....g.............
...............g..
g.............x...
............g.....
................g.
17 16
................
................
................
................
................
........g.......
................
................
................
................
................
................
..x.............
................
................
................
................
6 6
...gxg
....gg
..g.g.
......
....g.
g.gg..
17 16
..g.gg.....g....
......gg........
.........g....g.
................
................
.......g........
.............g..
......x.........
................
................
g........g.g....
................
................
...g............
................
............g...
................
3 10
..g.g..g..
..g.gg....
gx.gg.gggg
17 2
..
.x
..
..
..
..
..
..
..
..
..
..
..
..
..
..
..
9 12
............
............
............
............
g...........
............
g...g.......
....x.......
............
5 6
...g..
..g..x
......
.....g
g.....
2 9
..gg..gg.
ggx.gggg.
12 9
....gx...
.........
gg.......
.....g...
.........
..g......
g........
g..gg..g.
.........
..g....g.
.......g.
g........
3 10
......g.gg
.ggxgg.g.g
gg..g..gg.
1 12
g.....x.....
3 9
gg....x.g
g..g.....
gggg.gg..
10 18
.xgg..............
.........g........
.g................
..................
g.........g.......
...............ggg
..................
....g.............
..................
..................
11 14
..g..........g
...........g..
g..x...g....g.
g.............
.g........g...
............g.
......g....g..
..............
..............
..............
......g.......
20 19
...................
...................
...................
...................
...................
...................
...................
....x..............
...................
...................
....g......g.......
...................
...................
...................
...................
..................g
.g.................
........g..........
...................
...................
2 20
...........gg.......
.....g...g......x..g
2 19
ggg.g.xgg....g.....
...gg..gg...gg..g..
12 4
g.g.
.g.x
.g..
.gg.
.gg.
g.g.
..gg
....
....
....
....
.ggg
7 18
...........g......
..................
..........g.g.....
........gx........
.......g.g........
.g............g...
g.................
20 14
..............
........g.....
..............
..............
..........g...
...g..........
..............
..............
..............
..............
..............
..............
..............
g.............
..............
....g.........
...........g.x
..............
.............g
..............
12 13
...........g.
.......g.....
..g.......g..
.......g..g..
g..........x.
.............
.g...g.......
.............
..........g..
.............
.......g.....
........g....
6 9
.g.......
....g....
.........
gg.....x.
g........
.....g..g
16 4
....
....
....
....
g...
g..g
....
g...
...g
....
..g.
....
....
xg..
..g.
....
13 9
.........
......g..
.......g.
....g....
.........
.........
.........
.........
.........
.........
.........
...gx....
.......g.
15 20
....................
....................
.g.............g....
...g................
...............g....
....................
...........g........
..........g..g......
....................
..............g.....
g...................
..............g....g
...x.g.....g........
....................
....................
16 15
...............
.g..g..x...g...
g.....g........
...............
.....g.........
...............
...............
...............
...............
...............
..g............
...............
...............
...........g...
...............
...............
13 6
..g...
......
g.....
......
g.....
..g...
g.....
....g.
......
x....g
.....g
....gg
..gg.g
18 6
......
g.....
.....g
....g.
......
......
......
...g..
......
......
.....g
x....g
.g....
...gg.
...g..
......
......
......
9 2
.g
.g
gg
gg
..
..
gg
.g
x.
5 3
..g
x.g
gg.
.g.
g.g
3 19
...................
...g...............
.....xg..........gg
15 8
........
........
........
x.......
.g......
........
....g...
........
........
........
....g...
........
........
........
........
19 16
..............g.
...........g....
................
................
..........g.....
................
....g...........
................
..........g.....
g...........g...
...g............
................
................
................
................
................
................
.........x......
................
15 1
g
g
x
g
.
.
.
.
.
.
g
g
g
.
g
9 6
..g.g.
......
...g..
.gggg.
..gg..
....x.
..gg..
...g..
...gg.
5 17
.................
.................
.................
.................
..............x..
4 6
....g.
..g..g
gg.ggx
g.g.gg
19 2
..
x.
..
g.
..
.g
..
..
..
..
..
..
.g
..
g.
..
..
..
.g
5 14
.......x......
..............
..............
...g..........
..............
19 18
..................
................g.
..................
..........x.......
..................
..................
..................
..................
................g.
.....g............
............g.....
..................
..................
.........g........
..................
..................
..................
..................
..................
18 2
..
..
..
..
..
.g
.x
..
..
..
..
..
..
..
..
..
..
..
6 8
..gg.g..
........
..g.....
....g...
...gg...
.....x..
5 14
g..g.....g..g.
.g.......x....
.........g.g.g
....g....gg...
..g.....g.g...
16 17
..............g..
.........g.....g.
.................
...........gg...g
..........g......
.................
.................
.................
.................
..g.........g....
.................
.................
..g.....g.....g..
.................
..........x...g..
.................
18 1
g
x
.
.
g
.
.
.
.
.
.
.
.
g
.
.
.
.
17 12
............
.....g......
............
............
..g.g.....g.
............
............
..........g.
...........g
............
..........g.
............
.....g.g....
g........x..
.g..........
............
............
5 7
gxg....
.g.gggg
..gg.g.
g....g.
..g....
4 3
g..
xg.
..g
ggg
4 13
g.....g.g..g.
...gg..g...x.
.........g...
......g...g..
3 17
.................
.........xg......
.................
1 4
g.gx
18 17
.................
.................
.g...............
.................
...g.............
.................
..............g..
.................
.................
.gg..............
.................
.................
......g..........
...g...........x.
.....g...........
.................
.................
.................
18 12
............
..x.........
............
............
............
............
............
............
............
............
............
............
............
............
............
............
............
............
8 1
x
.
.
.
.
.
g
.
11 19
...................
...................
...g...........g...
...................
...................
..g................
.......g...........
......x............
...................
..............g....
...................
12 1
g
.
g
.
g
g
.
g
g
.
g
x
7 11
......g..g.
..g...gg...
..g....g...
........gg.
g.......x..
..........g
.......gg.g
stdout
Case 1: 20
Case 2: 76
Case 3: 26
Case 4: 54
Case 5: 40
Case 6: 16
Case 7: 12
Case 8: 30
Case 9: 26
Case 10: 84
Case 11: 44
Case 12: 40
Case 13: 42
Case 14: 30
Case 15: 42
Case 16: 40
Case 17: 0
Case 18: 16
Case 19: 54
Case 20: 12
Case 21: 52
Case 22: 36
Case 23: 4
Case 24: 86
Case 25: 66
Case 26: 36
Case 27: 12
Case 28: 94
Case 29: 66
Case 30: 20
Case 31: 46
Case 32: 54
Case 33: 12
Case 34: 84
Case 35: 46
Case 36: 64
Case 37: 32
Case 38: 0
Case 39: 2
Case 40: 44
Case 41: 128
Case 42: 80
Case 43: 98
Case 44: 14
Case 45: 28
Case 46: 110
Case 47: 36
Case 48: 0
Case 49: 18
Case 50: 22
Case 51: 24
Case 52: 66
Case 53: 42
Case 54: 12
Case 55: 34
Case 56: 78
Case 57: 78
Case 58: 66
Case 59: 44
Case 60: 50
Case 61: 40
Case 62: 62
Case 63: 86
Case 64: 74
Case 65: 38
Case 66: 46
Case 67: 50
Case 68: 124
Case 69: 68
Case 70: 56
Case 71: 54
Case 72: 34
Case 73: 18
Case 74: 32
Case 75: 16
Case 76: 84
Case 77: 30
Case 78: 38
Case 79: 0
Case 80: 30
Case 81: 34
Case 82: 8
Case 83: 48
Case 84: 2
Case 85: 28
Case 86: 76
Case 87: 112
Case 88: 28
Case 89: 76
Case 90: 34
Case 91: 12
Case 92: 50
Case 93: 2
Case 94: 6
Case 95: 72
Case 96: 0
Case 97: 12
Case 98: 48
Case 99: 38
Case 100: 66