TLE 50分求调
查看原帖
TLE 50分求调
1004460
OIer6666楼主2023/9/3 21:15

rt

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#define ll long long
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(0),cout.tie(0)
using namespace std;
map<int,map<int,ll>>s;
map<int,map<int,bool>>vis;
int nx,ny;int n,m;
int dx[]={0,1,-1,0,0,1,1,-1,-1};
int dy[]={0,0,0,1,-1,1,-1,1,-1};
void find_a_landmine(){
	s[nx][ny]=-1;
	for(int i=1;i<=8;i++){
		int tx=nx+dx[i];
		int ty=ny+dy[i];
		if(s[tx][ty]==0)
			s[tx][ty]=1;
	}
}
bool check(int nx,int ny){
	if(s[nx][ny]==-1){
		return false;
	}
	bool flag=true;
	for(int i=1;i<=8;i++){
		int tx=nx+dx[i];
		int ty=ny+dy[i];
		if(tx<0||ty<0||tx>n||ty>m){
			continue;
		}
		else if(s[tx][ty]==0){
			return false;
		}
	}
	return flag;
}
void dfs(int x,int y){
	vis[x][y]=1;
	for(int i=1;i<=8;i++){
		int tx=x+dx[i];
		int ty=y+dy[i];
		if(tx<0||ty<0||tx>n||ty>m||vis[tx][ty]==1||s[tx][ty]!=0){
			continue;
		}
		dfs(tx,ty);
	}
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	IOS;
	cin>>n>>m;
	for(int i=0;i<=n+1;i++)
		s[i][0]=s[i][m+1]=1;
	for(int i=0;i<=m+1;i++)
		s[0][i]=s[n+1][i]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			nx=i,ny=j;
			int a;cin>>a;
			if(a==1){
				find_a_landmine();
			}
		}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			nx=i,ny=j;
			if(vis[nx][ny]==1)
				continue;
			else if(s[nx][ny]==0){
				dfs(i,j);
//				cout<<i<<" "<<j<<endl;
				ans++;
			}else if(check(i,j)){
				ans++;
//				cout<<i<<" "<<j<<endl;
			}
		}
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){
//			printf("%3d",s[i][j]);
//		}
//		puts("");
//	}
	cout<<ans;
	return 0;
}
2023/9/3 21:15
加载中...