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