近日做题总结
P1789 MC插火把 一道简单的模拟题
大致有三种题解吧：
1.暴力 2.抽象问题 3.打表
1.先说抽象问题
首先我最开始想到的是 因为火把延伸最多两个 然后我还懒得判断是否越界(其实是不太会) 而且起始点是1，1 不是 二维数组的0，0 那么我就在正常大小的数组外面再开两圈让我无论在原本大小的哪个角落都不会发生越界问题 并通过-1 调整至数组下标 再通过+2 变成加圈后 数组里面的新下标 还需要注意一点就是最后算方块的时候，因为你总个数多了 你用所有的求一定会造成 0 多的情况 所以 要卡住最后筛选的范围
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int a[200][200];
int c[200];int d[200];
//int e[200];int f[200];
//说实在这种方法挺麻烦的不推荐哦
int main(){
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
//memset(d,0,sizeof(e));
//memset(d,0,sizeof(f));
int n,m,k; cin>>n>>m>>k;
int x,y,o,p;
for(int i=0;i<=m-1;i++)
cin>>c[i]>>d[i]; //减去1 变回正常的 加上2 额外分配两个大小
for(int i=0;i<=m-1;i++){
x=c[i]+1; y=d[i]+1;
for(int j=x-1;j<=x+1;j++)
for(int k=y-1;k<=y+1;k++)
a[j][k]=1;
a[x][y-2]=1;a[x][y+2]=1; a[x-2][y]=1; a[x+2][y]=1;}
for(int i=0;i<=k-1;i++){
cin>>c[i]>>d[i];
o=c[i]+1; p=d[i]+1;
for(int j=o-2;j<=o+2;j++){
for(int k=p-2;k<=p+2;k++)
a[j][k]=1;
}}
int sum=0;
for(int i=2;i<=n+1;i++){
for(int j=2;j<=n+1;j++){
//cout<<a[i][j];
if(a[i][j]!=0) sum++;
}
//cout<<endl;
//cout<<sum<<endl;
}
cout<<n*n-sum;
return 0;
}
总思路：我处理的总思路是 因为开始1，1 调成数组是0，0 但是我又扩增了2圈所以是再加2 如果输入的是c[i] 那么x是c[i]+1 -1+2
火把是 x-1 x+1 y-1 y+1 九宫格加四角 萤石没说的x-2 x+2 y-2 y+2
最后遍历的时候也很有讲究 2，2开始 原来是1，1现在是-1+2 变成2原来是n,n-1+2 变成n+1 示意图如此
2.再说打表
打表我大致理解就是 它主要分为x的 -1 -2 0 1 2 y的-1 -2 0 1 2坐标变换 用两个数组进行存储
int dx1[13]={2,0,-2,0,1,1,1,0,0,0,-1,-1,-1},//横坐标
dy1[13]={0,2,0,-2,0,1,-1,1,0,-1,0,1,-1};//纵坐标
int dx2[25]={-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},//横坐标
dy2[25]={-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};//纵坐标
之后就只需要在知道一个点的坐标之后 分别遍历不同的dx dy就能使更新照亮范围内的所有的点。
不提供完整代码仅提供思路 区别之处就在于坐标即数组下标x y x-1 y-1 x-2 y-2里面的0 -1 -2 都用dx dy 进行替代了
3.仅提供暴力的思路此处不提供代码。。。。
4.总结：这道题做完应该掌握的是那种格子题目的处理，包括判断越界 可以是一个bool函数 再结合题意去判断 这可以应用到很多同类型的题目里面 如扫雷等
bool pd(int x,int y){
if(x<0||y<0||y>=n||x>=n) return 0;
return 1;
//具体判断越界条件依题目而定
}
5.结合判断越界函数我能写出的最优解法是
#include <iostream>
#include <string.h>
using namespace std;
int a[105][105]; //最大100
int c[105];int d[105];
int n,m,k,x,y;
bool pd(int x, int y) { //判断是否越界
if(x < 1 || y < 1 || x > n || y > n) return 0;
return 1;
}
int main(){
cin>>n>>m>>k;
for(int i=0;i<=m-1;i++){
cin>>c[i]>>d[i];
int x=c[i];int y=d[i];
for(int j=x-1;j<=x+1;j++)
for(int k=y-1;k<=y+1;k++)
a[j][k]=1;
//9+4 九宫格加四角
if(pd(x,y-2))a[x][y-2]=1;
if(pd(x,y+2))a[x][y+2]=1;
if(pd(x-2,y))a[x-2][y]=1;
if(pd(x+2,y))a[x+2][y]=1;
}
for(int i=0;i<=k-1;i++){
cin>>c[i]>>d[i];
int x=c[i]; int y=d[i];
for(int j=x-2;j<=x+2;j++){
for(int k=y-2;k<=y+2;k++)
if(pd(j,k))
a[j][k]=1;
}}
int sum=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j]!=0) sum++;
}
}
cout<<n*n-sum;
return 0;
}
https://www.luogu.com.cn/problem/P1789
一道红题而已 不难 题解也有写的更好的
只是通过这种方式记录思维模式
希望对大家有所帮助！！！