NEU1682 全球变暖（bfs+dfs）
source link: https://arminli.com/neu1682/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
NEU1682 全球变暖（bfs+dfs）
February 07, 2016
中文题。有两种方法：
第一种：枚举所有海洋的点，bfs 搜索，标记陆地的点是第几天被淹没，然后 DFS 连通分量。
#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, t;
int pic[2005][2005];
int vis[2005][2005];
int dir[4][2] = {0,1,0,-1,1,0,-1,0};
bool judge(int x, int y){
if(x>=0 && x<n && y>=0 && y<m)
return true;
else return false;
}
void dfs(int x, int y, int cnt){
if(!judge(x, y) || vis[x][y] || !pic[x][y]) return;
vis[x][y] = 1;
for(int i = 0; i < 4; i++){
int x1 = x+dir[i][0];
int y1 = y+dir[i][1];
dfs(x1, y1, cnt);
}
}
int main(){
//freopen("a.txt", "r", stdin);
while(scanf("%d %d %d", &n, &m, &t) != EOF){
queue<int> q;
for(int i = 0; i < n; i++){
char ch[2005];
scanf("%s", ch);
for(int j = 0; j < m; j++){
if(ch[j] == '#')
pic[i][j] = -1;
else{
q.push(i*m+j);
pic[i][j] = 0;
}
}
}
for(int i = 0; i < n; i++){
if(pic[i][0] == -1){
pic[i][0] = 1;
q.push(i*m);
}
if(pic[i][m-1] == -1){
pic[i][m-1] = 1;
q.push(i*m+m-1);
}
}
for(int i = 0; i < m; i++){
if(pic[0][i] == -1){
pic[0][i] = 1;
q.push(i);
}
if(pic[n-1][i] == -1){
pic[n-1][i] = 1;
q.push(m*(n-1)+i);
}
}
while(!q.empty()){
int f = q.front();
q.pop();
int x = f/m; int y = f%m;
for(int i = 0; i < 4; i++){
int x1 = x+dir[i][0];
int y1 = y+dir[i][1];
if(judge(x1, y1) && pic[x1][y1] == -1){
pic[x1][y1] = pic[x][y]+1;
q.push(x1*m+y1);
}
}
}
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(pic[i][j] <= t)
pic[i][j] = 0;
memset(vis, 0, sizeof(vis));
int num = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(pic[i][j] && !vis[i][j])
dfs(i, j, ++num);
cout << num <<endl;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(!pic[i][j])
cout << ".";
else cout << "#";
}
cout << endl;
}
}
return 0;
}用 queue 写 bfs 的话 1.7s 过的，如果用数组搞 bfs 只有 0.7s，差距非常感人。
第二种方法：在搜索连通分量之前，并不需要 bfs，正反各遍历一遍图，就可以标记完成。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
int dis[4][2]={ {0,1},{0,-1},{1,0},{-1,0}};
char mp[2010][2010];
int TM[2010][2010];
bool vis[2010][2010];
int m,n,t;
struct mm{
int x,y;
};
void bfs(int x,int y){
queue <mm> q;
mm st;
st.x=x;
st.y=y;
vis[x][y]=1;
q.push(st);
while(!q.empty()){
mm now=q.front();
q.pop();
mm next;
for(int i=0;i<4;i++){
next.x=now.x+dis[i][0];
next.y=now.y+dis[i][1];
if(!vis[next.x][next.y]&&TM[next.x][next.y]>t){
vis[next.x][next.y]=1;
q.push(next);
}
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d%d%d",&n,&m,&t)!=EOF){
memset(vis,0,sizeof(vis));
memset(TM,0,sizeof(TM));
for(int i=0;i<n;i++){
scanf("%s",mp[i]);
}
for(int j=0;j<m;j++){
if(mp[0][j]=='.'){
TM[0][j]=0;
}
else{
TM[0][j]=1;
}
mp[0][j]='.';
if(mp[n-1][j]=='.'){
TM[n-1][j]=0;
}
else{
TM[n-1][j]=1;
}
mp[n-1][j]='.';
}
for(int i=1;i<n-1;i++){
if(mp[i][0]=='.'){
TM[i][0]=0;
}
else{
TM[i][0]=1;
}
mp[i][0]='.';
if(mp[i][m-1]=='.'){
TM[i][m-1]=0;
}
else{
TM[i][m-1]=1;
}
mp[i][m-1]='.';
}
for(int i=1;i<n-1;i++){
for(int j=1;j<m-1;j++){
if(mp[i][j]=='.'){
TM[i][j]=0;
}
else{
int k=1000000;
k=min(k,TM[i-1][j]+1);
//k=min(k,TM[i+1][j]+1);
k=min(k,TM[i][j-1]+1);
//k=min(k,TM[i][j+1]+1);
TM[i][j]=k;
//printf("%d %d %dn",i,j,k);
}
}
}
/*for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
printf("%d",TM[i][j]);
}
printf("n");
}*/
for(int i=n-2;i>0;i--){
for(int j=m-2;j>0;j--){
if(mp[i][j]=='.'){
TM[i][j]=0;
}
else{
int k=1000000;
k=min(k,TM[i-1][j]+1);
k=min(k,TM[i+1][j]+1);
k=min(k,TM[i][j-1]+1);
k=min(k,TM[i][j+1]+1);
TM[i][j]=k;
}
}
}
int ans=0;
for(int i=1;i<n-1;i++){
for(int j=1;j<m-1;j++){
if(!vis[i][j]&&mp[i][j]=='#'&&TM[i][j]>t){
ans++;
bfs(i,j);
}
}
}
/*for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
printf("%d",TM[i][j]);
}
printf("n");
}*/
printf("%dn",ans);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(TM[i][j]<=t){
printf(".");
}
else{
printf("#");
}
}
printf("n");
}
}
return 0;
}第二种方法只有 0.5s
Recommend
-
30
新浪科技讯北京时间3月26日消息，据国外媒体报道，全球气候变化是一个巨大的问题，并且情况还在不断恶化当中。冰山在不断消融，但是人类对于这个问题的重视程度还远未达到与这个问题严重程度相适应的地步。世界各国必须在一段相对较短的时期内努力实现能源
-
25
新浪科技讯北京时间9月18日消息，据国外媒体报道，一位知名科学家声称，全球变暖可能意味着种族差异的终结，因为气候变化将导致大规模的人类迁徙。美国莱斯大学的生物学家斯科特·所罗门（ScottSolomon）认为，在未来125年内，肤色很深或很
-
41
全球变暖新苦主？研究：2050年香蕉或完全消失
-
60
来源：中科院之声土壤是陆地生态系统储量最大的活跃碳库，植物将光合作用产物以凋落物（包括地上凋落物和地下根系）和根系分泌物的形式输入土壤，土壤有机质又在微生物调控下向大气释放CO2。全球气候变暖背景下，土壤碳库输入和输出的微小改变都可能较大程
-
44
新浪科技讯北京时间10月22日消息，据国外媒体报道，近期一项新研究指出，尽管某些局部地区的物种数量相对保持不变，但其物种组成却在迅速变化。地球不同地区的生物多样性危机有着明显差别。在全球范围内，物种正在以前所未有的速度消失。据估计，在没有人
-
12
前言 深度优先遍历（Depth First Search, 简称 DFS） 与广度优先遍历（Breath First Search）是图论中两种非常重要的算法，生产上广泛用于拓扑排序，寻路（走迷宫），搜索引擎，爬虫等，也频繁出现在 leetcode...
-
4
研究显示全球变暖迫使海洋生物“逃离”赤道 来源：新华网2021-04-09 14:52...
-
4
BFS & amp; DFS - What summit to start? advertisements I've read pages and pages of information on BFS and DFS algorithms. What none of the...
-
2
本文最后更新于 268 天前，文中所描述的信息可能已发生改变BFS，即 Breath First Search（广度优先搜索）DFS，即 Deep First Search （深度优先搜索）图的搜索是对于连通图的一种遍历...
-
2
搜索与图论篇——DFS和BFS 本次我们介绍搜索与图论篇中DFS和BFS，我们会从下面几个角度来介绍： DFS和BFS简介 DFS数字排序 DFS皇后排序 DFS树的重心 BFS走迷宫 BFS八数...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK