题目描述

暑假即将到来，鱼大大和羊大大计划吃肯德基。他们在计划中在某一天选择了某一个肯德基吃午饭。

到了约定的日子，鱼大大和羊大大都是$9$点出发，向KFC前进，问他们两能否在中午$12$点之前到达约定的KFC？如果可以，那么他们最少花费多少分钟就能在KFC相约？

约定：

时间计算：起点到终点的距离为时间，即走$1$单位的距离，鱼大大和羊大大都要花费$1$分钟的时间。

’@’ 是鱼大大的位置，’＃’ 是障碍，’F’ 表示KFC，’＆’ 表示羊大大的位置。

’.’，’F’，’@’ 和 ‘＆’，这些位置都可以通过。

输入格式
第一行包含两个整数 $n$ 和 $m$。

接下来的 $n$ 行，每行输入 $m$ 个字符来表示地图。($1 \le n \le m ≤ 200$)

输出格式
如果能找到一条可行的路径并在在$12$点之前到达KFC，输出花费的最少时间，否则输出 “Meeting cancelled”（两人无法在$12$点之前相约在此KFC）。

样例

Input 1

4 4 
@.#. 
.... 
.#.. 
F..&

Output 1

3

数据范围

见题面

思路：

这是一道很简单的BFS题，分别搜索两人到KFC的最少时间，取较大值

代码：

#include <bits/stdc++.h>
using namespace std;
int n, m;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
// 方向数组，这里就不多说了
char mp[205][205];   // 地图
bool vis[205][205];  // 标记数组
struct Point {
    int x, y, t;
    /* x和y：当前点的x坐标和y坐标  t：出发点距离当前点的最短长度 */
};
// bfs：如果能够到达KFC且不超时，就返回最短时间，否则返回-1
int bfs(int sx, int sy, int ex, int ey) {
  queue<Point> que;
  // 初始化，起点入队和标记
  que.push({sx, sy, 0});
  memset(vis, 0, sizeof vis);
  vis[sx][sy] = 1;
  while (que.size()) {
    // 取队头
    Point hd = que.front();
    que.pop();
    // 如果超时就返回-1
    if (hd.t >= 180) return -1;
    // 判断终点
    if (hd.x == ex && hd.y == ey) {
        return hd.t;
    }
    // 遍历四个方位（前后左右）
    for (int i = 0; i < 4; i++) {
      int nx = hd.x + dx[i];
      int ny = hd.y + dy[i];
      // 判断越界
      if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
      // 判断是否可以走
      if (mp[nx][ny] == '#' || vis[nx][ny]) continue;
      vis[nx][ny] = 1;
      // 新点入队
      que.push({nx, ny, hd.t + 1});
    }
  }
  // 如果没有返回，说明无法到达KFC，返回-1
  return -1;
}
int main() {
  int yux, yuy, yangx, yangy, endx, endy;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> mp[i][j];
      if (mp[i][j] == '@') {  // 记录鱼大大坐标
        yux = i;
        yuy = j;
      } 
      if (mp[i][j] == '&') {  // 记录羊大大坐标
        yangx = i;
        yangy = j;
      }
      if (mp[i][j] == 'F') {  // 记录终点坐标
        endx = i;
        endy = j;
      }
    }
  }
  // 分别搜索鱼大大和羊大大
  int timeyu = bfs(yux, yuy, endx, endy);
  int timeyang = bfs(yangx, yangy, endx, endy);
  // 如果有一人不能到达或超时，就取消
  if (timeyu == -1 || timeyang == -1) cout << "Meeting cancelled";
  // 输出所需时间的最大值
  else cout << max(timeyu, timeyang);
  return 0;
}