洛谷P1789题解

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

思路

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

分析样例

样例输入

CPP

5 1 0
3 3

样例输出

CPP

以下是我画的一张图（橙色部分为暗的区域）：

那么我们就可以来模拟这个过程了！

具体步骤

定义一个标记数组（因为用来标记，所以可以用布尔类型）。

CPP

bool vis[105][105];

确定偏移量，拿火把来举例：

CPP

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|光|光|
    |暗|光| 光 |光|暗|
    |暗|暗| 光 |暗|暗|
*/

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

CPP

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};

接下来，如果当前坐标不越界，那么就可以标记当前位置了：

CPP

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;//标记
	}
}

萤石同理：

CPP

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;
	}
}

接下来就是最后一步了：统计未被标记的数量。

CPP

for(int i=1;i<=n;i++)
{
	for(int j=1;j<=n;j++)
	{
		if(!vis[i][j])//如果这个数没有被标记 
		{
			cnt++;//那么就让计数器加1 
		}
	}
}

完整代码

CPP

#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;
}

完结撒花！

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

文章操作

洛谷P1789题解

思路

分析样例

具体步骤

完整代码

相关推荐

评论

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