题解：P1789 【Mc生存】插火把

· · 题解

洛谷P1789题解

题目传送门

感谢@MINMIN_找出向量图的问题。

思路

用标记数组标记有光和放置萤石或火把的区域，然后统计未被标记的数量即可。

分析样例

样例输入

5 1 0
3 3

样例输出

12

以下是我画的一张图（橙色部分为暗的区域）： 那么我们就可以来模拟这个过程了！

具体步骤

  1. 定义一个标记数组（因为用来标记，所以可以用布尔类型）。 
    bool vis[105][105];
  2. 确定偏移量，拿火把来举例： 
    const int h_dx[]={-2,-1,-1,-1,0,0,0,0,0,1,1,1,2};
const int h_dy[]={0,-1,0,1,-2,-1,0,1,2,-1,0,1,0};
/*
h_dx代表x[i]的偏移量，h_dy代表y[i]的偏移量。比如说-2加上当前的x和0加上当前的y就相当于在（x-2,y）的位置上 
也就是说到了标A的位置上：
|暗|暗| A  |暗|暗|
|暗|光| 光 |光|暗|
|光|光|x ,y|光|光|
|暗|光| 光 |光|暗|
|暗|暗| 光 |暗|暗|
*/

    那么萤石的偏移量就好办了：

const int y_dx[]={-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2};
const int y_dy[]={-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2};
  1. 接下来，如果当前坐标不越界，那么就可以标记当前位置了： 
    for(int j=0;j<13;j++)
{
int sx=x+h_dx[j];//当前坐标=x+（火把）偏移量
int sy=y+h_dy[j];//当前坐标=y+（火把）偏移量
if(sx>=1&&sx<=n&&sy>=1&&sy<=n)//判断是否越界
{
    vis[sx][sy]=1;//标记
}
}

    萤石同理：

for(int j=0;j<25;j++)
{
    int sx=x+y_dx[j];
    int sy=y+y_dy[j];
    if(sx>=1&&sx<=n&&sy>=1&&sy<=n)
    {
        vis[sx][sy]=1;
    }
}
  1. 接下来就是最后一步了：统计未被标记的数量。 
    for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
    if(!vis[i][j])//如果这个数没有被标记 
    {
        cnt++;//那么就让计数器加1 
    }
}
}

    完整代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k,x,y,cnt=0;
bool vis[105][105];
const int h_dx[]={-2,-1,-1,-1,0,0,0,0,0,1,1,1,2};//火把偏移量 
const int h_dy[]={0,-1,0,1,-2,-1,0,1,2,-1,0,1,0};//火把偏移量 
const int y_dx[]={-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2};//萤石偏移量 
const int y_dy[]={-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2};//萤石偏移量
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        for(int j=0;j<13;j++)
        {
            int sx=x+h_dx[j];//当前坐标=x+（火把）偏移量
            int sy=y+h_dy[j];//当前坐标=y+（火把）偏移量
            if(sx>=1&&sx<=n&&sy>=1&&sy<=n)
            {
                vis[sx][sy]=1;//标记 
            }
        }
    }
    for(int i=1;i<=k;i++)
    {
        cin>>x>>y;
        for(int j=0;j<25;j++)
        {
            int sx=x+y_dx[j];//当前坐标=x+（萤石）偏移量
            int sy=y+y_dy[j];//当前坐标=y+（萤石）偏移量
            if(sx>=1&&sx<=n&&sy>=1&&sy<=n)
            {
                vis[sx][sy]=1;//标记 
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(!vis[i][j])//如果这个数没有被标记 
            {
                cnt++;//那么就让计数器加1 
            }
        }
    }
    cout<<cnt;
    return 0;
}

完结撒花！