题目链接:https://www.luogu.org/problemnew/show/U23217
题目
题目背景
yizimi的宝藏是数学的奥秘……
(待完善正解,将来可能会SPJ)
题目描述
yizimi在一个岛上降落,他有一个遥感器,显示他所在的坐标x,y,显示了n * m的地图:地图上显示0,则此坐标位置为海洋,地图上显示1~9,则为海拔为显示数字的陆地。
yizimi发现周围有许多岛屿,包括他自己所在的岛屿,不过他去不了除自己所在岛屿以外的地方。他要寻求的宝藏是他可以去到的所有坐标位置的海拔的乘积,取模100007。
不过他还想知道他所在的岛屿的面积与所给地图的中有几个岛屿。
输入输出格式
输入格式:
第1行:n,m 地图行数列数
第2~n+1行:为m个用空格隔开的数字,代表各地海拔。
第n+2行:x,y yizimi所在第x行,第y列
输出格式:
第一行:所在岛屿面积(每个点3分)
第二行:岛屿个数(每个点3分)
第三行:yizimi的数字宝藏(每个点4分)
说明
对于100%的数据:2<=n,m<=1000
保证yizimi跳伞不会跳到海里去
题目分析
首先,要注意这道题
有三问!!!!!!
第一问是一道很简单的连通块的问题,通过DFS。
第二问是一个关于染色的问题,要染几种颜色才能染完除0外的所有点。
第三问是第一问的升级版,只是把计数变为了数字乘积而已。
所以,此题的重点就是在搜索上。
本道题DFS与BFS都适用。本体街使用的是DFS。
具体实现
求简单的连通块
这个说实话不用多讲,用DFS,枚举每一个方向的可行性,进行下一步扩展,在扩展过程中标记、计数、计算乘积。
inline void dfs1(int x,int y){ for(int i=1;i<=4;i++){ int nx=x+dx[i],ny=y+dy[i]; if(nx>n || nx<1 || ny>m || ny<1) continue; if(a[nx][ny]>0 && !bb[nx][ny]){ ans1++; ans2=(ans2*a[nx][ny])%mod; //cout<<ans2<<"\n"; bb[nx][ny]=true; dfs1(nx,ny); } } }
求连通块的个数
就是枚举所有点所在的连通块,用一个负数标记,每次把大于0的坐标及其连通块染色,继续枚举。
枚举
int color=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(b[i][j]>0) color--,bbb[i][j]=true,b[i][j]=color,dfs2(i,j,color);
染色
inline void dfs2(int x,int y,int color){ for(int i=1;i<=4;i++){ if(nx<=n && nx>=1 && ny<=m && ny>=1 && b[nx][ny]>0){ b[nx][ny]=color; bbb[nx][ny]=true; dfs2(nx,ny,color); } } }
完整代码
依然有自己的代码特点
define狂魔
中间注释是测试代码用的。
#include<bits/stdc++.h> using namespace std; #define go(i,j,n,k) for(register int i=j;i<=n;i+=k) #define fo(i,j,n,k) for(register int i=j;i>=n;i-=k) #define mn 1010 #define nx x+dx[i] #define ny y+dy[i] #define inf 1<<30 #define mod 100007 inline int read(){ int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int a[mn][mn],b[mn][mn]; bool bb[mn][mn],bbb[mn][mn]; int n,m,startx,starty,ans1,ans2; const int dx[5]={0,0,0,-1,1}; const int dy[5]={0,-1,1,0,0}; inline void dfs1(int x,int y){ go(i,1,4,1){ if(nx>n || nx<1 || ny>m || ny<1) continue; if(a[nx][ny]>0 && !bb[nx][ny]){ ans1++; ans2=(ans2*a[nx][ny])%mod; //cout<<ans2<<"\n"; bb[nx][ny]=true; dfs1(nx,ny); } } } inline void dfs2(int x,int y,int color){ go(i,1,4,1){ if(nx<=n && nx>=1 && ny<=m && ny>=1 && b[nx][ny]>0){ b[nx][ny]=color; bbb[nx][ny]=true; dfs2(nx,ny,color); } } } int main(){ //freopen("xiaodao001.in","r",stdin); //freopen("xiaodao001.out","w",stdout); memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(bb,0,sizeof(bb)); n=read(),m=read(); //cout<<n<<" "<<m<<"\n"; go(i,1,n,1) go(j,1,m,1) b[i][j]=a[i][j]=read(); startx=read(),starty=read(); /* cout<<n<<" "<<m<<"\n"; go(i,1,n,1){ go(j,1,m,1) cout<<a[i][j]<<" "; cout<<"\n"; } cout<<startx<<" "<<starty<<"\n"; */ bb[startx][starty]=true; ans1++,ans2=a[startx][starty]; dfs1(startx,starty); int color=0; go(i,1,n,1) go(j,1,m,1) if(b[i][j]>0) color--,bbb[i][j]=true,b[i][j]=color,dfs2(i,j,color); cout<<ans1<<"\n"<<-color<<"\n"<<ans2<<"\n"; /*go(i,1,n,1){ go(j,1,m,1) cout<<b[i][j]<<" "; cout<<"\n"; }*/ return 0; }