样例过了,全错
  • 板块P3395 路障
  • 楼主socool
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/28 18:47
  • 上次更新2024/12/28 21:55:16
查看原帖
样例过了,全错
826799
socool楼主2024/12/28 18:47

这个应该怎么改啊?

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
typedef struct s
{
  int x, y, t;
} s;
typedef pair<int, int> pii;
vector<pii> p;
queue<s> q;
const int N = 1010;
bool g[N][N];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

bool bfs(int n)
{
  // 初始化
  g[0][0] = 1;
  q.push({0, 0, 0});

  while (q.size())
  {
    // 取队头
    int xh = q.front().x;
    int yh = q.front().y;
    int th = q.front().t;
    q.pop();
    if (xh == n - 1 && yh == n - 1)
      return 1;
    // 拓展队头
    for (int i = 0; i < 4; i++)
    {
      int x = xh + dx[i], y = yh + dy[i];
      if (x >= 0 && y >= 0 && x < n && y < n && g[x][y] == 0)
      {
        q.push({x, y, th + 1});
        g[x][y] = 1;
      }
    }
    // 放置障碍
    if (th < p.size())
      g[p[th].first][p[th].second] = 1;
  }

  return 0;
}

int main()
{
//输入
  int T;
  cin >> T;
  while (T--)
  {
    int n;
    cin >> n;
    for (int i = 0; i < 2 * n - 2; i++)
    {
      int x, y;
      cin >> x >> y;
      x--, y--;
      p.push_back({x, y});
    }
//搜索
    if (bfs(n))
      cout << "Yes";
    else
      cout << "No";
//清零
    p.clear();
    while (q.size())
      q.pop();
    memset(g, 0, sizeof g);
  }
  return 0;
}
2024/12/28 18:47
加载中...