全RE求助qwq 疑似爆栈
  • 板块P3395 路障
  • 楼主8atemak1r
  • 当前回复10
  • 已保存回复10
  • 发布时间2022/1/25 21:25
  • 上次更新2023/10/28 10:57:20
查看原帖
全RE求助qwq 疑似爆栈
305121
8atemak1r楼主2022/1/25 21:25
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int t, n;
struct node{
    int x, y, t;
    // bool operator < (const node &a) const{return a.x < x;}
};
// map<node, int> mp;
vector<node> vv;
int mp[2005][2005];
struct nd{
    int x, y, t;
};
// queue<nd> q;
int xx[4] = {1, 0, -1, 0}, yy[4] = {0, 1, 0, -1};
bool inmap(int x, int y) {
    return x > 0 && x <= n && y > 0 && y <= n;
}
bool vis[15][2005][2005];
bool flag;
void bfs(int t) {
    queue<nd> q;
    q.push((nd){1, 1, 0});
    while(!q.empty()) {
        nd tmp = q.front(); q.pop();
        // cout << tmp.x << ' ' << tmp.y << '\n';
        if(tmp.x == n && tmp.y == n) {
            // while(!q.empty()) q.pop();
            flag = true;
            return;
        }
        for(int i = 0; i < 4; ++ i) {
            int nx = tmp.x + xx[i], ny = tmp.y + yy[i];
            if(inmap(nx, ny) == false || (mp[nx][ny] != 0 && mp[nx][ny] < tmp.t + 1) || vis[t - 1][nx][ny]) continue;
            q.push((nd){nx, ny, tmp.t + 1}); vis[t - 1][nx][ny] = true;
        }
    }
    return;
}
int main() {
    cin >> t;
    while(t --) {
        cin >> n;
        int u, v;
        for(int i = 1; i <= (2 * n - 2); ++ i) {
            cin >> u >> v;
            vv.push_back((node){u, v, i});
            mp[u][v] = i;
        }
        vis[t - 1][1][1] = 1;
        flag = false; bfs(t);
        if(flag) cout << "Yes\n";
        else cout << "No\n";
        for(int i = 0; i < vv.size(); ++ i) mp[vv[i].x][vv[i].y] = 0;
        while(!vv.empty()) vv.pop_back();
    }
    return 0;
}
/*


*/
2022/1/25 21:25
加载中...