DIV2 1000pt
题意：一个由n*m的网格组成的棋盘，有四种点，'.'表示空点，'#'表示是墙不能走，'$'表示起点(同样是空点)，'1'~'9'表示该点有复活时间为t的怪兽。每次，可以从一个点走到其上下左右的四个点，只要他们在棋盘上且不是墙，这样记为走了一步。如果走到的点有怪兽i，则杀死它，在杀死该怪兽以后，如果人又走了ti步(ti为该怪兽的复活时间)则该怪兽会复活，如果第ti步恰好走回到含有怪兽i的该点，则怪兽i会被再次杀死。问最少要多少步，才能使得整个棋盘上所有怪物同时处于死亡状态。如果不行，输出-1。
n, m <= 50
解法：1、因为复活时间为1-9，所有最多有9个怪物。
2、如果从这些已知的某个怪物出发，则最多有9!中可能的路径。
所以得到解法，首先用BFS预处理出点'$'到所有怪物的最短距离，再预处理出每个怪物到其他怪物的最短距离，这一步时间复杂度最多O(10×50×50)。然后枚举出发的怪兽，求出从该怪兽出发，到使得所有怪物同时死亡所需要的最短时间，该时间加上'$'到出发怪兽的距离即为所求最短距离。
为了方便编码时处理怪兽复活问题，所以枚举出发怪兽的时候，可以写成枚举在哪个怪兽那里结束，然后倒推。
tag:BFS, DFS
1 // BEGIN CUT HERE 2 /* 3 * Author: plum rain 4 * score : 5 */ 6 /* 7 8 */ 9 // END CUT HERE 10 #line 11 "SlimeXResidentSlime.cpp" 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 #include 23 #include 24 #include 25 #include 26 #include 27 #include 28 #include 29 #include 30 #include 31 #include
VI; 48 typedef vector
VS; 49 typedef vector VD; 50 typedef long long int64; 51 typedef pair pii; 52 53 const double eps = 1e-8; 54 const double PI = atan(1.0)*4; 55 const int maxint = 2139062143; 56 57 struct bfs_nod{ 58 int x, y, d; 59 }; 60 61 struct Nod{ 62 Nod(int xx, int yy, int cc){ 63 x = xx; y = yy; c = cc; 64 } 65 int x, y, c; 66 }; 67 68 int dir[4][2] = { {-1, 0}, { 1, 0}, { 0, -1}, { 0, 1}}; 69 70 pii stt; 71 int ans, n, m, nod_sz; 72 map mp; 73 bool v[100][100]; 74 bool vis[100]; 75 int d[20][20]; 76 vector nod; 77 VS A; 78 bfs_nod an[10000]; 79 80 bool cmp(Nod a, Nod b) 81 { 82 return a.c < b.c; 83 } 84 85 bool ok(int x, int y) 86 { 87 if (x < 0 || y < 0) return 0; 88 if (x >= n || y >= m) return 0; 89 return A[x][y] != '#'; 90 } 91 92 void BFS (int x, int y, int pos) 93 { 94 CLR (v); 95 v[x][y] = 1; 96 97 int l = 0, r = 0; 98 bfs_nod tmp; tmp.d = 1; 99 for (int i = 0; i < 4; ++ i) 100 if (ok(x+dir[i][0], y+dir[i][1])){101 int tx = x + dir[i][0], ty = y + dir[i][1];102 if (v[tx][ty]) continue;103 tmp.x = tx; tmp.y = ty;104 v[tx][ty] = 1;105 an[r++] = tmp;106 }107 108 while (l < r){109 tmp = an[l++];110 if (mp.count(MP(tmp.x, tmp.y))){111 int num = mp[MP(tmp.x, tmp.y)];112 d[num][pos] = d[pos][num] = tmp.d;113 }114 115 ++ tmp.d;116 for (int i = 0; i < 4; ++ i)117 if (ok(tmp.x+dir[i][0], tmp.y+dir[i][1])){118 bfs_nod tmp2 = tmp;119 int tx = tmp2.x + dir[i][0], ty = tmp2.y + dir[i][1];120 if (v[tx][ty]) continue;121 tmp2.x = tx; tmp2.y = ty;122 v[tx][ty] = 1;123 an[r++] = tmp2;124 }125 }126 }127 128 void DFS (int p, int len, int num)129 {130 if (num == nod_sz){ 131 if (d[10][p] > 0)132 ans = min(ans, len + d[10][p]);133 return ;134 }135 136 vis[p] = 1;137 for (int i = 0; i < nod_sz; ++ i)138 if (!vis[i] && d[p][i] > 0 && len+d[p][i] < nod[i].c)139 DFS (i, len+d[p][i], num+1);140 vis[p] = 0;141 }142 143 class SlimeXResidentSlime144 {145 public:146 int exterminate(vector AA){147 A = AA;148 n = A.size(); m = A[0].size();149 nod.clear();150 for (int i = 0; i < n; ++ i)151 for (int j = 0; j < m; ++ j){152 if (A[i][j] == '.' || A[i][j] == '#') continue;153 if (A[i][j] == '$'){154 stt.first = i; stt.second = j;155 }156 else157 nod.PB(Nod(i, j, A[i][j]-'0'));158 }159 if (nod.size() > 9) return -1;160 sort (nod.begin(), nod.end(), cmp);161 162 nod_sz = nod.size();163 mp.clear();164 for (int i = 0; i < nod_sz; ++ i)165 mp[make_pair(nod[i].x, nod[i].y)] = i;166 mp[stt] = 10;167 168 CLR1 (d);169 BFS (stt.first, stt.second, 10);170 for (int i = 0; i < nod_sz; ++ i)171 BFS (nod[i].x, nod[i].y, i);172 173 ans = maxint;174 for (int i = 0; i < nod_sz; ++ i){175 CLR (vis);176 DFS (i, 0, 1);177 }178 if (ans == maxint) return -1;179 return ans;180 }181 182 // BEGIN CUT HERE183 public:184 //void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); }185 void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0();}186 private:187 template string print_array(const vector &V) { ostringstream os; os << "{ "; for (typename vector ::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }188 void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }189 void test_case_0() { string Arr0[] = 190 { ".##.###..#....##.#.#......##...#.#....#####.#....#", "####..#####.####..#....###.#..######.##.#.#.##..##", ".##.#####.#.#####.#.###....#.##..##.##.#...######.", ".#.####.#..#.###.#.#....#.#.#.##.#.#..###..#.####.", "###.#.##....#..#..#.##..#####.####..##..#.#.#.#...", "....##.###...#####.#..#.######..####..#.##.#..###.", "######.##.#.##...#..#.#####..#..##.#.#.##.##.#....", "####.###..##.##.##..##..##.#####.#.####.#.##...###", "#.....#.###..#...#.###....#..#.#.#.##.#####.#....#", "###.###.##.#..#..###.###..##...#...#.##.#.####..#.", "..#....#..#..##.##...#....####.......#.####..#..##", ".#.....####.#.##.#.#.#..##.#.#.......####.$.###.##", "#####..#.#.##..#...##.#..##....#.##.##.#....##.###", "#.####...###.##.#..#.#....#.....#.#..###..#..##..#", ".#.##.#...########.#.......#..#..###.###.#.#.##.#.", ".##....#...##..##...#.#...#....##.##..#.....#.##..", "..##...###..#..#####..#.##..#.#.#..#.#....#.###.#.", ".####...##...#.##..#.#.#.#...###....######.....###", "#..##.###....#..###...####..#####.##.##.#.#..##...", "##...#..###..#.#.#.#.#...#.#.....###..#.#..#...###", "..#####.#.####..##.........##...###...#..###.#.###", "#.####.#..##....######..##.#.#...#..#..##..#.#...#", "...##.#..###....##.#.....#..#.#..#..##.#.....#...#", ".....#...#.#..###..##.##.....#.#..#.##.###.####.#.", ".#.#.#.#.####....#.##...#.###.###.#..#..#.###....#", ".#...#...#.....##.#..#.#...#.###..#...#.##.#..#.##", "#..##.#.##.##.####.##.##1.##...#.#...####..#.###.#", "#.##...###.##....####.##.###.##..##.#.#.#.#.#.....", ".......###...#.####....#..###..#.#.####...##.#####", "####..#..######........#..######.####.#...#.....##", "#######..#####...##..#.#...##..##..##.##.##.#...#.", "##..###.....#.#######..#.#...####....#.####.....##", "##.##...#.###.##.#.###...#....###....###..#####.#.", "#...#.###..#....#.###......#.#..##.#..##.....#.#.#", ".#.#.##..#..#..######.#.9...###.#.#..#.#####...#..", "#.##.#.###.####.###...#.#..####.....##.##.###...##", "#.....##.##....#######...#...#..#.##.#.#.##....###", "###.#.#.##.....#.#..###.#.#..#...##.##.###...##..#", "#.....##.#.#.####.#....##..##.#....##.##...#######", "..#...##..#.#####...#.#.##...##....#.#..#.#.#....#", "#.###...#####.##..##.##..##.###.####.#..#.#..#...#", "####.###...####.#..#..#....#.######.#.##.......#.#", "..#...#.....###....#####.##.##..#.#..#..##.##..#.#", ".###..##.#.#...###.#..#....##..#.#.#..#.#.##.#..##", ".####....#...##.##...###.##...########.#.....##.##", ".#.#######.###...#.....#.##..#.#..#####.#.##..##..", "#.##..#.##.##.####.#.#.#####...##.#.#.##.###...##.", ".###.#.#.#......####..##.##.#.#.#####.###.##...#..", ".#.#.#....#..#.#...#.#.....###...#...#.###......##", "#.##.###..###..#.#...#.######.#.##...##.#..#..####"}; vector Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = -1; verify_case(0, Arg1, exterminate(Arg0)); }191 void test_case_1() { string Arr0[] = {192 "$",193 "1",194 "1"}; vector Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = -1; verify_case(1, Arg1, exterminate(Arg0)); }195 void test_case_2() { string Arr0[] = {196 "$124"}; vector Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 5; verify_case(2, Arg1, exterminate(Arg0)); }197 void test_case_3() { string Arr0[] = { "$.#2"198 ,"#..1"}; vector Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 6; verify_case(3, Arg1, exterminate(Arg0)); }199 200 // END CUT HERE201 202 };203 204 // BEGIN CUT HERE205 int main()206 {207 //freopen( "a.out" , "w" , stdout ); 208 SlimeXResidentSlime ___test;209 ___test.run_test(-1);210 return 0;211 }212 // END CUT HERE View Code