题目描述
由于全球变暖，岛国S的沿岸的海水不断上涨，形式岌岌可危。
S国的地图是由n*m个网格组成的，网格由.和#组成，#代表的区域是陆地，.和地图外面全是海水。
每天，海水将侵蚀相邻的陆地，即如果陆地与海水相邻的话，第二天就会变成海水。这里面的两块相邻表示两块之间公用一条边。
比如S国的地图是这样的：
..###...
..###...
..###...
...##...
..######
..######
...#####
那么一天后，S国就变成了这样：
........
...#....
...#....
........
...##...
...####.
........
这种悲剧每天都在发生，再过1天S国就将被海水吞没。
现在S国的领导想知道t天后S国将变成什么样，有几块岛屿。。 如果两块陆地属于同一岛屿，当且仅当两块陆地相邻。
比图上面1天后S的地图中有两块岛屿。
输入
多组样例数入（样例不多）。
第一行是n,m,t，题目中已描述。（1<=n,m,t,<=2000）
然后是一个n行m列的S国地图，由.和#组成。
输出
第一行一个整数x表示岛屿数。
接下来n行画出t天后S国的地图。
样例输入
7 8 1
..###...
..###...
..###...
...##...
..######
..######
...#####
样例输出
2 ........ ...#.... ...#.... ........ ...##... ...####. ........
这道 题目代码量还是很大的。
bfs+dfs
类似于 白书上的Fire!
/* *********************************************** Author :guanjun Created Time :2016/3/8 8:53:07 File Name :neu1682.cpp ************************************************ */ #include <iostream> #include <cstring> #include <cstdlib> #include <stdio.h> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <iomanip> #include <list> #include <deque> #include <stack> #define ull unsigned long long #define ll long long #define mod 90001 #define INF 0x3f3f3f3f #define maxn 10010 #define cle(a) memset(a,0,sizeof(a)) const ull inf = 1LL << 61; const double eps=1e-5; using namespace std; struct node{ int x,y; }; char mp[2010][2100]; int vis[2010][2010]; int dir[4][2]={1,0,0,1,0,-1,-1,0}; int n,m,t; void dfs(int x,int y){ for(int i=0;i<4;i++){ int nx=x+dir[i][0]; int ny=y+dir[i][1]; if(!vis[nx][ny]&&nx<=n&&nx>=1&&ny<=m&&ny>=1&&mp[nx][ny]=='#'){ vis[nx][ny]=1; dfs(nx,ny); } } } void print(){ int ans=0; cle(vis); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(mp[i][j]=='#'&&!vis[i][j]){ vis[i][j]=1; dfs(i,j); ans++; } } } printf("%d ",ans); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) printf("%c",mp[i][j]); printf(" "); } } void bfs(){ queue<node>q; int tmp=1;node u; t--; for(int i=0;i<=n+1;i++){ mp[i][0]='.'; mp[i][m+1]='.'; } for(int i=0;i<=m+1;i++){ mp[0][i]='.'; mp[n+1][i]='.'; } for(int i=0;i<=n+1;i++){ for(int j=0;j<=m+1;j++){ if(mp[i][j]=='.'&&!vis[i][j]){ for(int k=0;k<4;k++){ int nx=i+dir[k][0]; int ny=j+dir[k][1]; // cout<<nx<<" "<<ny<<endl; if(nx<=n&&nx>=1&&ny<=m&&ny>=1){ if(mp[nx][ny]=='#'){ //cout<<nx<<" "<<ny<<endl; node w;w.x=nx;w.y=ny; q.push(w); mp[nx][ny]='.'; //u.x=i,u.y=j,q.push(u); vis[nx][ny]=1; } } } vis[i][j]=1; } } } if(t==0){ print(); } else{ queue<node>p; //cout<<t<<endl; while(t--){ while(!q.empty()){ node v=q.front();q.pop(); // cout<<v.x<<" "<<v.y<<endl; for(int i=0;i<4;i++){ int nx=v.x+dir[i][0]; int ny=v.y+dir[i][1]; if(nx<=n&&nx>=1&&ny<=m&&ny>=1){ if(mp[nx][ny]=='#'){ mp[nx][ny]='.';u.x=nx,u.y=ny; p.push(u); } } //vis[nx][ny]=1; } } if(p.empty())break; while(!p.empty()){ q.push(p.front());p.pop(); } } print(); } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif //freopen("out.txt","w",stdout); while(cin>>n>>m>>t){ for(int i=1;i<=n;i++){ scanf("%s",mp[i]+1); } bfs(); } return 0; }