UVA 11624

• 因为人和火不能模拟出来同时走,
• 那么bfs 火 到个点的时间,
• 然后bfs 人 到个点的时间,判断时间是否满足在火到来之前
• 终点就是越界
• memset(timefire,0x3d,sizeof timefire),我当时设置的是memset(timefire,0,sizeof)就wa了

  #include <iostream>
  #include <string.h>
  #include <queue>
  
  using namespace std;
  const int maxn = 1e3 + 10;
  struct node {
      int x,y;
      int step;
      node(){}
      node(int a,int b,int c) {
          x = a; y = b; step = c;
      }
  };
  
  int sx,sy;
  int n,m;
  int next1[4][2] = {0,1,1,0,0,-1,-1,0};
  char grid[maxn][maxn];
  int timefire[maxn][maxn];
  bool vis[maxn][maxn];
  queue<pair<int,int> > qfire;
  
  void bfs_fire(){
      while ( !qfire.empty() ) {
          int x = qfire.front().first;
          int y = qfire.front().second;
          qfire.pop();
  
          for (int i=0; i<4; i++) {
              int tx = x + next1[i][0];
              int ty = y + next1[i][1];
              if (tx<1 || ty<1 || tx>n || ty>m) continue;
              if (grid[tx][ty] == '#' || vis[tx][ty]) continue;
              
              vis[tx][ty] = 1;
              timefire[tx][ty] = timefire[x][y] + 1;
              qfire.push({tx,ty});
              
          }
      }
  }
  
  void bfs() {
  	memset(vis,0,sizeof vis);
      queue<node> que;
      vis[sx][sy] = 1;
      que.push( node(sx,sy,0) );
  
      while ( !que.empty() ) {
          node cur = que.front();
          que.pop();
          
          for(int i=0; i<4; i++) {
              int tx = cur.x + next1[i][0];
              int ty = cur.y + next1[i][1];
              if (tx<1 || ty<1 || tx>n || ty>m) {
  				cout << cur.step+1 << endl;
  				return ;
  			}
              if (grid[tx][ty] == '#' || vis[tx][ty] || cur.step+1 >= timefire[tx][ty]) continue;
              
              vis[tx][ty] = 1;
              que.push( node(tx,ty,cur.step + 1) );
          }
      }
      cout << "IMPOSSIBLE" << endl;
      return ;
  }
  void init() {
      memset(vis,0,sizeof vis);
      memset(timefire,0x3f,sizeof timefire);
  }
  int main() {
  //	freopen("a.txt","r",stdin);
      int times;
      cin >> times;
      while (times--) {
          init();
          cin >> n >> m;
          for (int i=1; i<=n; i++)
              for (int j=1; j<=m; j++) {
                  cin >> grid[i][j];
                  if (grid[i][j] == 'J') {
                      sx = i;
                      sy = j;
                  }
                  else if (grid[i][j] == 'F') {
                      vis[i][j] = 1;
                      timefire[i][j] = 0;
                      qfire.push({i,j});
                  }
              }
          bfs_fire();
          bfs();
      }
      return 0;
  }