题解 P2691 【逃离】

易颖杰 · 2018-01-13 22:29:41 · 题解

这道题，蒟蒻的思路其实并不是很完美，本来想看看能骗多少分，结果0ms跑完满分，这道题仔细分析后蒟蒻发现，可以把这歌矩阵分成许多嵌套的小矩阵每一个矩阵里的点能不能全出来就看它最外面的的一圈的出口数是否大于等于里面的点的个数，是就可以，不是就不可以，然后逻辑上把最外层的点消除，那么里面又是一个矩阵，这样的话就可以一层一层的消去所有的点，不过这思路有反例，想知道的私信我。好了，详情看代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=40;
int n,map[N][N],m;
int work(int l)
{
    int found=0;//found是最外层点的个数
    for(int i=1+l;i<=n-l-1;i++)//找点
    {
        if(map[i][1+l]) found++;
        if(map[n-l][i]) found++;
        if(map[i][n-l]) found++;
        if(map[1+l][i]) found++;
    }
    if(map[1+l][1+l]) found--;//重复寻找的要减掉
    if(map[n-l][n-l]) found++;//上面的循环没循环到的位置
    m-=found;//删除外层点
    found=(n-l*2-2)*4-found;//算出出口个数
    return found;
}
bool solve()
{
    for(int i=0;i<=(n%2 ? n/2-1:n/2-2);i++)//枚举层数，但是要特判奇偶
        if(work(i)<m)//里面的点比出口多......
            return 0;//返回false
    return 1;//可以全部到达边缘
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        map[x][y]=1;//起始点标记
    }
    if(solve()) printf("YES\n");
    else printf("NO\n");
    return 0;
}