洛谷 P4961

题目
思路
Code

题目

戳

为了小埋A了这道题。

思路

读入原来的矩阵，将不是雷的格子更新为数字（数字就是该格子周围八格的雷的个数）将是雷的格子赋值为inf。然后就按照题目要求计算周围八格没有“空格”的“数字”个数和“空"的个数。

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<iomanip>

#include<algorithm>

using namespace std;

const int inf=0x3f3f3f;

int n,m,sum1,sum2;

int dx[10]={0,1,-1,1,1,-1,-1,0,0},dy[10]={0,0,0,1,-1,1,-1,1,-1};

bool map0[1001][1001];

int map1[1001][1001];

inline int read(){

	int x=0;

	bool f=0;

	char c=getchar();

	while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}

	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

	return f?-x:x;

}//读优

void js(int x,int y){

	int sum=0;

	for(int i=1;i<=8;++i){

		int c=x+dx[i],d=y+dy[i];

		if(c>0&&c<=n&&d>0&&d<=m&&map0[c][d]) sum++;

	}

	map1[x][y]=sum;

}//更新数字的函数

bool pd(int x,int y){

	bool qaq=0;

	for(int i=1;i<=8;++i){

		int c=x+dx[i],d=y+dy[i];

		if(c>0&&c<=n&&d>0&&d<=m&&map1[c][d]==0){

			qaq=1;

			break;

		}

	}

	if(qaq) return false;

	return true;

}

void k(int x,int y){

	map1[x][y]=-1;

	for(int i=1;i<=8;++i){

		int c=x+dx[i],d=y+dy[i];

		if(c>0&&c<=n&&d>0&&d<=m&&map1[c][d]==0){

			k(c,d);

		}

	}

}

int main(){

	n=read();m=read();

	for(int i=1;i<=n;++i){

		for(int j=1;j<=m;++j){

			map0[i][j]=read();

			if(map0[i][j]) map1[i][j]=inf;

		}

	}//读入，和预处理。

	for(int i=1;i<=n;++i){

		for(int j=1;j<=m;++j){

			if(!map0[i][j]) js(i,j);

		}

	}//更新数字。

	for(int i=1;i<=n;++i){

		for(int j=1;j<=m;++j){

			if(map1[i][j]!=0&&map1[i][j]!=inf){

				if(pd(i,j)) sum1++;

			}

		}

	}//计算周围八格没有空格的个数

	for(int i=1;i<=n;++i){

		for(int j=1;j<=m;++j){

			if(map1[i][j]==0){

				k(i,j);

				sum2++;

			}

		}

	}//计算空的个数

	cout<<sum1+sum2;

	return 0;

}

巴特西

洛谷 P4961

题目

思路

Code

最新文章

热门文章