P3395 路障

标签：int memset bfs 路障 P3395 include true

P3395 路障
bfs

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2010;

int n;
bool st[N][N];
int sx[N], sy[N];   //存的是t时刻路障的坐标
bool g[N][N];
int t;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

struct node 
{
    int x, y, t;
};    //运用结构体存坐标和时间

bool bfs(int x, int y, int t)
{
    st[x][y] = true;
    
    queue<node> q;
    node now = {x, y, t};                //定义一个当前状态的结构体
    
    q.push(now);
    
    while(!q.empty())
    {
        node u = q.front();
        q.pop();
        
        if(u.x == n && u.y == n) return true;    //找到答案返回true
      
        //为什么要出队的时候判断，而入队的时候判断第一个测试点会wa？
        g[sx[u.t]][sy[u.t]] = true;              //标记下一个时间点放障碍的坐标，用来判断下一个时间点是否有障碍是否能走
        for(int i = 0; i < 4; i ++)
        {
            int a = u.x + dx[i], b = u.y + dy[i];
            if(a >= 1 && a <= n && b >= 1 && b <= n && g[a][b] == false && st[a][b] == false)
            {
                st[a][b] = true;
                u = {a, b, ++ u.t};         //注意这里的 u.t = u.t + 1,  不能写成 u = {a, b, t};     
                q.push(u);
            }
        }
    }
    return false;
}

int main ()
{
    int T;
    cin >> T;
    
    while(T --)
    {
        memset(st, 0, sizeof st);    //多组数据注意memset
        memset(g, 0, sizeof g);
        cin >> n;
        for(int i = 1; i <= (2 * n - 2); i ++)
        {
            cin >> sx[i] >> sy[i];
        }
        
        if(bfs(1, 1, 1)) puts("Yes");
        else puts("No");

        //bfs(1, 1, 1)表示从1，1开始走，走到下一个点时间为1
    }
    
    return 0;
}

心得体会：

1. 学习本题中 sx[i], sy[i] 表示 i时刻放的路障的坐标，用空间换时间，直接用数组的下标表示时间，值表示坐标
2. 结构体存三个变量 x, y, t
3. 注意多组数据， memset清空

标签：int,memset,bfs,路障,P3395,include,true
From： https://www.cnblogs.com/fxc2002/p/17014735.html