P3395 路障

    • 257通过
    • 1.5K提交
  • 题目提供者 阮行止 管理员
  • 评测方式 云端评测
  • 标签 广度优先搜索,BFS 模拟 O2优化 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    此题约为NOIP提高组Day1T1难度。

    题目描述

    B君站在一个 $n\times n$ 的棋盘上。最开始,B君站在(1,1)这个点,他要走到(n,n)这个点。

    B君每秒可以向上下左右的某个方向移动一格,但是很不妙,C君打算阻止B君的计划。

    每秒结束的时刻,C君会在(x,y)上摆一个路障。B君不能走在路障上。

    B君拿到了C君准备在哪些点放置路障。所以现在你需要判断,B君能否成功走到(n,n)

    保证不会走到某处,然后被一个路障砸死。

    输入输出格式

    输入格式:

    首先是一个正整数T,表示数据组数。

    对于每一组数据:

    第一行,一个正整数n

    接下来2n-2行,每行两个正整数xy,意义是在那一秒结束后,(x,y)将被摆上路障。

    输出格式:

    对于每一组数据,输出YesNo,回答B君能否走到(n,n)

    输入输出样例

    输入样例#1: 复制
    2
    
    2
    1 1
    2 2
    
    5
    3 3
    3 2
    3 1
    1 2
    1 3
    1 4
    1 5
    2 2
    输出样例#1: 复制
    Yes
    Yes

    说明

    样例解释:

    以下0表示能走,x表示不能走,B表示B君现在的位置。从左往右表示时间。

    Case 1:
    0 0    0 0    0 B  (已经走到了)
    B 0    x B    x 0 
    Case 2:
    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0
    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0    0 0 0 0 0
    0 0 0 0 0    0 0 x 0 0    0 0 x 0 0    0 0 x 0 0
    0 0 0 0 0    0 0 0 0 0    0 0 x 0 0    0 0 x 0 0
    B 0 0 0 0    0 B 0 0 0    0 0 B 0 0    0 0 x B 0 ......(B君可以走到终点)

    数据规模:

    防止骗分,数据保证全部手造。

    对于20%的数据,有n<=3

    对于60%的数据,有n<=500

    对于100%的数据,有n<=1000

    对于100%的数据,有T<=10

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。