作战计划题解

作战计划

时间限制：1秒 内存限制：128M

题目描述

“革命已经到了最关键的时刻，同志们需要更加努力！”。

将军在沙盘前面正在思考…

为了达到更好的作战效果，现在需要与另一支部队进行汇合，并且需要时刻避开敌人的封锁圈。

简单来看，沙盘是一个N*M大小的地图，并且标注了我军、友军、敌军的位置。

我军在地图以M标注，友军在地图以G标注，敌军在地图上以Z标注，由于敌人过于狡猾，他们在很多地方已经埋了许多地雷，地雷以X标注，其余位置以.标注。注意：地雷区域是及其危险的，我军和友军是不能走的。

我军的机动化程度比较高，每天可以移动3个单位的距离，友军以步兵著称，每天只能移动1个单位的距离（移动只能上下左右的进行）。敌军每天可以向四周搜寻扩张2个单位的距离（地雷就是敌人埋的，因此地雷不会阻挡他们搜寻扩张的脚步），即经过k天后所有与敌人的曼哈顿距离不超过2∗k的地方都会被敌人占领。

我军和右军为了保险起见，每天都会指挥队伍在敌人扩张之后再进行移动。

请你求一下在不被敌人发现的前提下，两军会合的最短时间。

输入描述

讯享网

第一行一个T，表示T组测试数据。

对于每组数据：

第一行包含两个整数N和M，表示地图大小。

然后输入N行M列字符，表示沙盘地图中的情况（一定只有一个我军，一个友军，两个敌人）。

输出描述

对于每组数据，输出一行，若能回合，则输出最短时间，否则输出-1。

输入样例

3 5 6 XXXXXX XZ..ZX XXXXXX M.G... ...... 5 6 XXXXXX XZZ..X XXXXXX M..... ..G... 10 10 .......... ..X....... ..M.X...X. X......... .X..X.X.X. .........X ..XX....X. X....G...X ...ZX.X... ...Z..X..X 

输出样例

讯享网1 1 -1 

数据范围

1<N,M<8001<N,M<800

这道题可以用双向BFS来解决

敌军会随时扩张，而我军与友军也在随时移动，终点不固定。这样我们就可以用双向BFS，友军设为一个起点，我军设维另一个起点，共同去找终点，按照’t从1寻找最短时间。根据题目描述，需避开地雷与敌人扩张的领域，但是敌人可以走地雷：地雷我们可以用一个bool类型二维数组去记录，来判断该点是否能走；敌人的扩张怎么解决呢？因为敌人每次先移动，而且每次扩张2格，所以这时我们只需要判定(x, y)点到敌人的距离 >= 2t即可。

说了这么多

上代码！

Accepted

# include <cstdio> # include <cstring> # include <cmath> # include <algorithm> # include <vector> # include <iostream> # include <string> # include <set> # include <map> # include <stack> # include <queue> # include <deque> # define pf push_front # define pb push_back # define ppf pop_front() # define ppb pop_back() # define mp make_pair # define p_a first # define p_b second # define PI acos(-1, 0) # define LF putchar('\n') # define SP putchar(' ') # define repi(a, b) for(short i = (a); i <= (b); i++) # define repi_(a, b) for(short i = (a); i >= (b); i--) # define repj(a, b) for(short j = (a); j <= (b); j++) # define repj_(a, b) for(short j = (a); j >= (b); j--) # define repk(a, b) for(short k = (a); k <= (b); k++) # define repk_(a, b) for(short k = (a); k >= (b); k--) # define WW(x) while((x)--) # define paix(a, n) sort((a) + 1, (a) + 1 + (n)); # define BUG(z) cout << endl << (z) << endl; # define lowbit(z) ((z) & (-z)) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; const int N1 = 1e6 + 5, N2 = 1e3 + 5, M1 = 1e9 + 7, M2 = , INF1 = 0x7fffffff, INF2 = 0x3f3f3f3f; const ll INF = ; template <typename T> void read(T& x) { 
    x = 0; char ch = getchar(); ll f = 1; while (!isdigit(ch)) { 
    if (ch == '-') f *= -1; ch = getchar(); } while (isdigit(ch)) { 
    x = x * 10 + ch - 48; ch = getchar(); } x *= f; } template <typename T, typename... Args> void read(T& first, Args&... args) { 
    read(first); read(args...); } template <typename T> void write(T arg) { 
    T x = arg; if (x < 0) { 
    putchar('-'); x = -x; } if (x > 9) write(x / 10); putchar(x % 10 + '0'); } template <typename T, typename... Ts> void write(T arg, Ts... args) { 
    write(arg); if (sizeof...(args) != 0) { 
    putchar(' '); write(args...); } } void CLOSE() { 
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); } // ————————————————————分割线~~~  const short dx[] = { 
   0, 1, 0, -1}; const short dy[] = { 
   -1, 0, 1, 0}; // 方向数组  struct node { 
    short x, y, s; } w, g, e[2]; // 我军、友军以及两个敌军的位置 int T, n, m; short st[N2][N2]; // st[][]存储我军与友军已到达的点 bool a[N2][N2]; // a[][]存储地雷位置  bool check(short x, short y, short t) { 
    // check()判断(x, y)点的到敌军的曼哈顿距离，< 2t那么会被敌军抓到 repi(0, 1) if (fabs(e[i].x - x) + fabs(e[i].y - y) <= (t << 1)) return false; return true; } bool BFS(queue <node> &q, short t, short v) { 
    // BFS()判断我与友军是否会合，能会合返回true，反之返回false while(!q.empty() && q.front().s < t * v) { 
    node tmp = q.front(); q.pop(); if (!check(tmp.x, tmp.y, t)) continue; repi(0, 3) { 
    short xx = tmp.x + dx[i], yy = tmp.y + dy[i]; if (xx < 0 || yy < 0 || xx >= n || yy >= m || !a[xx][yy] || !check(xx, yy, t)) continue; if (!st[xx][yy]) q.push({ 
   xx, yy, tmp.s + 1}); else if (st[xx][yy] != st[tmp.x][tmp.y]) return true; st[xx][yy] = st[tmp.x][tmp.y]; } } return false; } int bfs() { 
    // bfs()寻找与友军会合的最短时间，会被敌军抓到返回-1 memset(st, 0, sizeof(st)); queue <node> qw, qg; qw.push(w), qg.push(g); st[w.x][w.y] = 1, st[g.x][g.y] = 2; for(int t = 1; !qw.empty() || !qg.empty(); t++) if (BFS(qw, t, 3) || BFS(qg, t, 1)) return t; return -1; } void init() { 
    // 初始化地图 short cnt = 0; repi(0, n - 1) { 
    getchar(); repj(0, m - 1) { 
    char ch = getchar(); if (ch == 'Z') e[cnt++] = { 
   i, j, 0}; else if (ch == 'M') w = { 
   i, j, 0}; else if (ch == 'G') g = { 
   i, j, 0}; else a[i][j] = ch != 'X'; } } return ; } signed main() { 
    /* freopen("", "r", stdin); freopen("", "w", stdout); */ scanf("%d", &T); WW(T) { 
    scanf("%d%d", &n, &m); init(); write(bfs()); LF; } /* fclose(stdin); fclose(stdout); */ return 0; }