返回题解分享
讨论 / 题解分享/ 帖子详情

全球变暖(编程题) - 题解

###### 测试数据与题目不符,有界限的问题

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n;
vector<vector<char>>arr1;
vector<vector<char>>arr2; 
vector<pair<int,int>>dao;
map<pair<int,int>,bool> vis;
set<int> num;
set<int> num2;
map<pair<int,int>,int> f;
vector<vector<int>>dir = {{-1,0},{1,0},{0,-1},{0,1}};
void dfs(pair<int,int> node ,int flag){
	if(vis[node]){
		return ;	
	}
	f[node] = flag;
	vis[node] = true;
	num.insert(flag);
	for(int i=0;i<4;i++){
		int x =node.first + dir[i][0];
		int y = node.second + dir[i][1];
		if(x<0||y<0||x>=n||y>=n) continue;
		if(arr1[x][y]=='.'){
			arr2[node.first][node.second] = '.';
		}
		if(arr1[x][y]=='#'&&!vis[{x,y}]){
			dfs(pair<int,int>({x,y}),flag);
		}
	}
	
}


signed main(){
//	int n;
	cin>>n;
	arr1 = vector<vector<char>>(n,vector<char>(n));
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>arr1[i][j];
			if(arr1[i][j]=='#'){
				dao.push_back({i,j});
			}
		}
	}
	arr2 = arr1;
	int flag = 1;
	for(auto& e:dao){
		dfs(e,flag);
		flag++;
	}
	for(auto& e:dao){
		if(arr2[e.first][e.second] == '#'){
			num2.insert(f[e]);
		}
	}
	cout<<num.size() - num2.size();
	
	
	return 0;
}
0 回复 0 转发 0 喜欢 0 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!