oibh:拯救oibh总部 2024-04-01 17:11:47 0 0 题目背景 oibh 总部突然被水淹没了!现在需要你的救援…… 题目描述 oibh 被突来的洪水淹没了,还好 oibh 总部有在某些重要的地方起一些围墙。用 * 号表示,而一个四面被围墙围住的区域洪水是进不去的。 oibh 总部内部也有许多重要区域,每个重要区域在图中用一个 0 表示。 现在给出 oibh 的围墙建设图,问有多少个没被洪水淹到的重要区域。 输入格式 第一行为两个正整数 x,yx,y。 接下来 xx 行,每行 yy 个整数,由 * 和 0 组成,表示 oibh 总部的建设图。 输出格式 输出没被水淹没的 oibh 总部的 0 的数量。 输入输出样例 输入 #1复制4 50000000*000*0*000*00 输出 #1复制1 输入 #2复制5 5******0*0***0***0*0****** 输出 #2复制5 说明/提示 对于 100\0% 的数据,1 \le x,y \le 5001≤x,y≤500。 1.dp 我用 \large dp_{i,j}dpi,j 表示矩阵中ii行jj列的状态,其中: 如果 \large dp_{i,j}=1dpi,j=1 就表示矩阵中ii行jj列是墙; 如果 \large dp_{i,j}=0dpi,j=0 就表示矩阵中ii行jj列是当前未被淹没的空地; 相反,如果 \large dp_{i,j}=2dpi,j=2 就表示被淹没的空地。 然后,我们便可以把水淹没空地的过程抽象成被淹没的地将'被淹没'的状态转移给旁边空地的模型。 再说具体点,就是如果当前的 \large dp_{i,j}dpi,j 是2,就把它旁边的00也变成22,这就是深搜或宽搜的过程。 但是,我们可以对此过程进行一个优化,仔细想想,把刚才过程倒过来,就是: 如果当前的 \large dp_{i,j}dpi,j 是00且它四周有被淹没的地,或者说如果\large dp_{i,j}=0dpi,j=0且dp_{i-1,j}dpi−1,j或dp_{i+1,j}dpi+1,j或dp_{i,j-1}dpi,j−1或dp_{i,j+1}dpi,j+1中任意一个是22,则 \large dp_{i,j}dpi,j 应变为22. 那我们现在就可以把代码写出来了。 我还是放一下代码,供大家参考。 3.Code#include<bits/stdc++.h>using namespace std;int dp[505][505],n,m,ans,last;char ch;int main(void){cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){std::cin>>ch;if(ch=='*')dp[i][j]=1;//输入 }}for(int i=1;i<=n;i++){if(dp[i][1]==0)ans++,dp[i][1]=2;if(dp[i][m]==0)ans++,dp[i][m]=2;//初始化 }for(int i=1;i<=m;i++){if(dp[1][i]==0)ans++,dp[1][i]=2;if(dp[n][i]==0)ans++,dp[n][i]=2;//同上 }while(1){last=ans;ans=0;//一遍遍转移状态 for(register int i=1;i<=n;i++){for(register int j=1;j<=m;j++){if(dp[i][j]==0&&(dp[i-1][j]==2||dp[i+1][j]==2||dp[i][j-1]==2||dp[i][j+1]==2)){dp[i][j]=2;//状态转移 }}}for(register int i=1;i<=n;i++){for(register int j=1;j<=m;j++){if(dp[i][j]==0)ans++;//统计答案 }}if(last==ans){cout<<ans;return 0;//输出并退出 }}return 0;} 2.DFS 首先我们要想清楚我们搜索的是什么 我们搜索的应该是会被淹到的部分,一旦找到会被淹到的部分,就把它变成‘*’。 所以这题就很像找 联通块!!! 所以,我们的代码应该是:#include<iostream>#include<fstream>#include<algorithm>#include<cmath>#include<string>#include<cstring>#include<cstdio>#include<cstdlib>//#pragma GCC optimize(3)//sort(st.begin(),st.end());using namespace std;int xx[10]={0,0,-1,1};int yy[10]={1,-1,0,0};int n,m,gs;char ch[510][510];void dfs(int x,int y){if(x<1||y<1||x>n||y>m||ch[x][y]=='*')return;//边界ch[x][y]='*';//标记for(int i=0; i<4; i++)dfs(x+xx[i],y+yy[i]);//深度优先搜索}int main(){cin>>n>>m;for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin>>ch[i][j];dfs(1,1);for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) { if(ch[i][j]=='0') { gs++;}}cout<<gs; return 0;} 可当你信心满满的提交时,你就会收到luogu测评器给你的拥抱!! 想知道为什么吗? 看看我下面出的这个数据:5 50*000*0000000000000000000 你会发现他给出的答案是22。????? 那是因为我们刚搜到第一个0后就搜不下去了。 所以我想到了一个新办法: 多搜一圈!!!#include<iostream>#include<fstream>#include<algorithm>#include<cmath>#include<string>#include<cstring>#include<cstdio>#include<cstdlib>//#pragma GCC optimize(3)//sort(st.begin(),st.end());using namespace std;int xx[10]={0,0,-1,1};int yy[10]={1,-1,0,0};int n,m,gs;char ch[510][510];void dfs(int x,int y){if(x<0||y<0||x>n+1||y>m+1||ch[x][y]=='*')return;ch[x][y]='*';for(int i=0; i<4; i++)dfs(x+xx[i],y+yy[i]);}int main(){cin>>n>>m;for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin>>ch[i][j];dfs(0,0);//多搜一圈for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) { if(ch[i][j]=='0') { gs++;}}cout<<gs; return 0;} 收藏(0)