题解 P7309 [COCI2018-2019#2] Kocka

· · 题解

题目传送门：

P7309 [COCI2018-2019#2] Kocka

题意：

在一个干净的平面方格纸上，是否存在一种放置障碍物的方式，使得从前后左右四个方向看到的第一个障碍物前空出的方格数满足输入要求。

分析：

先来看看什么时候一定不存在：

  1. 相反的两个方向障碍物前空出的方格数相加不小于 n。

    例如，在一个 4\times 4 的方格纸上，第一行从左看，第一个障碍物前有 2 个空格；第一行从右看，第一个障碍物前也有 2 个空格，这显然不行对吧。

    对于同一行或列，如果它在某一方向上前有 i 个空格，则意味着该行或列第 i+1 个位置必定有一个障碍物，那么位于其相反的方向最多有 n-i-1 个空格，也就是 j\leq n-i-1 ,即 i+j<n , i+j\ngeq n。

  2. 相邻的两个方向上也会互相影响（这个不好直接归纳，详细见下）。

    例如下图：

    第 2 行从左看有 2 个空格，那么意味着第 2 行第 3 列位置一定有一个障碍物。但如果从上看第 3 列前的空格超过了一格或者从下看第 3 列前的空格超过了两格，那显然不可能。

思路:

对以上进行归纳。

对于左侧，第 i 个数据输入 L_i，意味着 (i,L_i+1)为一个障碍，接下来检验 (i,j+1) 到其他方向的空格数是否合法。

对于右侧，前面，后面同理。

代码：

#include <bits/stdc++.h>

using namespace std;
const int N=1e5;

int n,mp[4][N+5];

bool check(int i,int j){//判断障碍物放置坐标(i,j)是否合法
    if ((mp[0][i]==-1||mp[0][i]>=j)
        ||(mp[1][i]==-1||n-mp[1][i]<j)
        ||(mp[2][j]==-1||mp[2][j]>=i)
        ||(mp[3][j]==-1||n-mp[3][j]<i)){
            return 1;
        }
    return 0;
}
int main(){
    scanf("%d",&n);
    for (int i=0;i<4;i++)
        for (int j=1;j<=n;j++)
            scanf("%d",&mp[i][j]);
  //这里用了离线操作，其实在线也无妨
    for (int i=1;i<=n;i++){
        if((mp[0][i]!=-1&&check(i,mp[0][i]+1))
            ||(mp[1][i]!=-1&&check(i,n-mp[1][i]))
            ||(mp[2][i]!=-1&&check(mp[2][i]+1,i))
            ||(mp[3][i]!=-1&&check(n-mp[3][i],i))){
                return printf("NE\n"),0;
            }
    }
    printf("DA\n");
    return 0;
}