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