5
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
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK