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
// BEGIN CUT HERE
/*
* Author: plum rain
* score :
*/
/* */
// END CUT HERE
#line 11 "SlimeXResidentSlime.cpp"
#include <sstream>
#include <stdexcept>
#include <functional>
#include <iomanip>
#include <numeric>
#include <fstream>
#include <cctype>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <set>
#include <queue>
#include <bitset>
#include <list>
#include <string>
#include <utility>
#include <map>
#include <ctime>
#include <stack> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
#define CLR1(x) memset(x, -1, sizeof(x))
#define PB push_back
#define MP make_pair
#define SZ(v) ((int)(v).size())
#define zero(x) (((x)>0?(x):-(x))<eps)
#define out(x) cout<<#x<<":"<<(x)<<endl
#define tst(a) cout<<#a<<endl
#define CINBEQUICKER std::ios::sync_with_stdio(false) typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long int64;
typedef pair<int, int> pii; const double eps = 1e-;
const double PI = atan(1.0)*;
const int maxint = ; struct bfs_nod{
int x, y, d;
}; struct Nod{
Nod(int xx, int yy, int cc){
x = xx; y = yy; c = cc;
}
int x, y, c;
}; int dir[][] = {{-, }, {, }, {, -}, {, }}; pii stt;
int ans, n, m, nod_sz;
map<pii, int> mp;
bool v[][];
bool vis[];
int d[][];
vector<Nod> nod;
VS A;
bfs_nod an[]; bool cmp(Nod a, Nod b)
{
return a.c < b.c;
} bool ok(int x, int y)
{
if (x < || y < ) return ;
if (x >= n || y >= m) return ;
return A[x][y] != '#';
} void BFS (int x, int y, int pos)
{
CLR (v);
v[x][y] = ; int l = , r = ;
bfs_nod tmp; tmp.d = ;
for (int i = ; i < ; ++ i)
if (ok(x+dir[i][], y+dir[i][])){
int tx = x + dir[i][], ty = y + dir[i][];
if (v[tx][ty]) continue;
tmp.x = tx; tmp.y = ty;
v[tx][ty] = ;
an[r++] = tmp;
} while (l < r){
tmp = an[l++];
if (mp.count(MP(tmp.x, tmp.y))){
int num = mp[MP(tmp.x, tmp.y)];
d[num][pos] = d[pos][num] = tmp.d;
} ++ tmp.d;
for (int i = ; i < ; ++ i)
if (ok(tmp.x+dir[i][], tmp.y+dir[i][])){
bfs_nod tmp2 = tmp;
int tx = tmp2.x + dir[i][], ty = tmp2.y + dir[i][];
if (v[tx][ty]) continue;
tmp2.x = tx; tmp2.y = ty;
v[tx][ty] = ;
an[r++] = tmp2;
}
}
} void DFS (int p, int len, int num)
{
if (num == nod_sz){
if (d[][p] > )
ans = min(ans, len + d[][p]);
return ;
} vis[p] = ;
for (int i = ; i < nod_sz; ++ i)
if (!vis[i] && d[p][i] > && len+d[p][i] < nod[i].c)
DFS (i, len+d[p][i], num+);
vis[p] = ;
} class SlimeXResidentSlime
{
public:
int exterminate(vector <string> AA){
A = AA;
n = A.size(); m = A[].size();
nod.clear();
for (int i = ; i < n; ++ i)
for (int j = ; j < m; ++ j){
if (A[i][j] == '.' || A[i][j] == '#') continue;
if (A[i][j] == '$'){
stt.first = i; stt.second = j;
}
else
nod.PB(Nod(i, j, A[i][j]-''));
}
if (nod.size() > ) return -;
sort (nod.begin(), nod.end(), cmp); nod_sz = nod.size();
mp.clear();
for (int i = ; i < nod_sz; ++ i)
mp[make_pair(nod[i].x, nod[i].y)] = i;
mp[stt] = ; CLR1 (d);
BFS (stt.first, stt.second, );
for (int i = ; i < nod_sz; ++ i)
BFS (nod[i].x, nod[i].y, i); ans = maxint;
for (int i = ; i < nod_sz; ++ i){
CLR (vis);
DFS (i, , );
}
if (ans == maxint) return -;
return ans;
} // BEGIN CUT HERE
public:
//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(); }
void run_test(int Case) { if ((Case == -) || (Case == )) test_case_0();}
private:
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
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; } }
void test_case_0() { string Arr0[] =
{".##.###..#....##.#.#......##...#.#....#####.#....#", "####..#####.####..#....###.#..######.##.#.#.##..##", ".##.#####.#.#####.#.###....#.##..##.##.#...######.", ".#.####.#..#.###.#.#....#.#.#.##.#.#..###..#.####.", "###.#.##....#..#..#.##..#####.####..##..#.#.#.#...", "....##.###...#####.#..#.######..####..#.##.#..###.", "######.##.#.##...#..#.#####..#..##.#.#.##.##.#....", "####.###..##.##.##..##..##.#####.#.####.#.##...###", "#.....#.###..#...#.###....#..#.#.#.##.#####.#....#", "###.###.##.#..#..###.###..##...#...#.##.#.####..#.", "..#....#..#..##.##...#....####.......#.####..#..##", ".#.....####.#.##.#.#.#..##.#.#.......####.$.###.##", "#####..#.#.##..#...##.#..##....#.##.##.#....##.###", "#.####...###.##.#..#.#....#.....#.#..###..#..##..#", ".#.##.#...########.#.......#..#..###.###.#.#.##.#.", ".##....#...##..##...#.#...#....##.##..#.....#.##..", "..##...###..#..#####..#.##..#.#.#..#.#....#.###.#.", ".####...##...#.##..#.#.#.#...###....######.....###", "#..##.###....#..###...####..#####.##.##.#.#..##...", "##...#..###..#.#.#.#.#...#.#.....###..#.#..#...###", "..#####.#.####..##.........##...###...#..###.#.###", "#.####.#..##....######..##.#.#...#..#..##..#.#...#", "...##.#..###....##.#.....#..#.#..#..##.#.....#...#", ".....#...#.#..###..##.##.....#.#..#.##.###.####.#.", ".#.#.#.#.####....#.##...#.###.###.#..#..#.###....#", ".#...#...#.....##.#..#.#...#.###..#...#.##.#..#.##", "#..##.#.##.##.####.##.##1.##...#.#...####..#.###.#", "#.##...###.##....####.##.###.##..##.#.#.#.#.#.....", ".......###...#.####....#..###..#.#.####...##.#####", "####..#..######........#..######.####.#...#.....##", "#######..#####...##..#.#...##..##..##.##.##.#...#.", "##..###.....#.#######..#.#...####....#.####.....##", "##.##...#.###.##.#.###...#....###....###..#####.#.", "#...#.###..#....#.###......#.#..##.#..##.....#.#.#", ".#.#.##..#..#..######.#.9...###.#.#..#.#####...#..", "#.##.#.###.####.###...#.#..####.....##.##.###...##", "#.....##.##....#######...#...#..#.##.#.#.##....###", "###.#.#.##.....#.#..###.#.#..#...##.##.###...##..#", "#.....##.#.#.####.#....##..##.#....##.##...#######", "..#...##..#.#####...#.#.##...##....#.#..#.#.#....#", "#.###...#####.##..##.##..##.###.####.#..#.#..#...#", "####.###...####.#..#..#....#.######.#.##.......#.#", "..#...#.....###....#####.##.##..#.#..#..##.##..#.#", ".###..##.#.#...###.#..#....##..#.#.#..#.#.##.#..##", ".####....#...##.##...###.##...########.#.....##.##", ".#.#######.###...#.....#.##..#.#..#####.#.##..##..", "#.##..#.##.##.####.#.#.#####...##.#.#.##.###...##.", ".###.#.#.#......####..##.##.#.#.#####.###.##...#..", ".#.#.#....#..#.#...#.#.....###...#...#.###......##", "#.##.###..###..#.#...#.######.#.##...##.#..#..####"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = -; verify_case(, Arg1, exterminate(Arg0)); }
void test_case_1() { string Arr0[] = {
"$",
"",
""}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = -; verify_case(, Arg1, exterminate(Arg0)); }
void test_case_2() { string Arr0[] = {
"$124"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, exterminate(Arg0)); }
void test_case_3() { string Arr0[] = {"$.#2"
,"#..1"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[]))); int Arg1 = ; verify_case(, Arg1, exterminate(Arg0)); } // END CUT HERE }; // BEGIN CUT HERE
int main()
{
//freopen( "a.out" , "w" , stdout );
SlimeXResidentSlime ___test;
___test.run_test(-);
return ;
}
// END CUT HERE