关于宽搜的时间问题
  • 板块灌水区
  • 楼主DeusExMachina
  • 当前回复10
  • 已保存回复10
  • 发布时间2021/11/16 14:16
  • 上次更新2023/11/4 00:25:10
查看原帖
关于宽搜的时间问题
361833
DeusExMachina楼主2021/11/16 14:16
  #define pii pair <int, int>
  #define mp make_pair
  #define x first
  #define y second
  queue <pii> q;
  q.push (mp (n + 1, m + 1));
  while (!q.empty ()) {
    pii p = q.front ();
    q.pop ();
    // Q[p.x][p.y] = 2;
    if (p.x + 1 <= n + 1 && Q[p.x + 1][p.y] == 0) {
      Q[p.x + 1][p.y] = 2; // <1>
      q.push (mp (p.x + 1, p.y));
    }
    if (p.x - 1 >= n - h + 1 && Q[p.x - 1][p.y] == 0) {
      Q[p.x - 1][p.y] = 2; // <2>
      q.push (mp (p.x - 1, p.y));
    }
    if (p.y + 1 <= m + 1 && Q[p.x][p.y + 1] == 0) {
      Q[p.x][p.y + 1] = 2; // <3>
      q.push (mp (p.x, p.y + 1));
    }
    if (p.y - 1 >= 0 && Q[p.x][p.y - 1] == 0) {
      Q[p.x][p.y - 1] = 2; // <4>
      q.push (mp (p.x, p.y - 1));
    }
  }

在这一段代码中,我要是把后面标注 <1> <2> <3> <4> 的代码删掉,还原回注释掉的那个代码,就会从 AC 178ms 到 TLE 80pts(时间限制 1000ms)。

这个是为什么呢?为什么换一种写法就 T 了?

2021/11/16 14:16
加载中...