这题一看到应该就可以反应过来是搜连通块的题
搜法分为 和
先看样例发现是一串数字所以无法写以下代码
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
那该怎么办
//用字符呗
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
char c;
cin>>c;
a[i][j]=c-'0';
}
或者
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%1d",&a[i][j]);//%1d表示只读一位
输入完那就开始搜索吧
先讲
通常会用到队列
这里我推荐一个 的双向队列，叫做
/*
队列基本操作：
deque<int> q;创建一个数双端队列q,int也可以是别的类型
q.empty();判断队列是否为空，为空返回true
q.push_front(s);将s从队头入队
q.push_back(s);将s从队尾入队,和普通队列方式一样
q.front();只返回队头元素
q.back();只返回队尾元素
q.pop_front();将队头元素弹出
q.pop_back;将队尾元素弹出
q.clear();将队列清空
*/
是一层一层搜的 框架如下
//bfs模板
struct ed
{
.....
}
deque<ed>q;
void bfs()
{
标记起点
起点入队列
while(!q.empty())//队列不为空
{
ed nw=q.front();//返回队首
for(拓展出接下来可能的状态)
{
ed nxt;
记录这一状态
判断状态是否合法
标记状态
q.push_back(nxt);//状态入队列
}
q.pop_front();//弹出队首
}
}
所以这题bfs写法如下
#include<bits/stdc++.h>
using namespace std;
struct pp
{
int x,y;
};
deque<pp> q;//队列
int n,m,ans=0;//n行m列，ans为答案
int a[105][105];//存矩阵
bool used[105][105];//记录是否走过
int dx[4]={-1,1,0,0};//向上下左右走一步行号和列好的改变
int dy[4]={0,0,-1,1};
void bfs(int sx,int sy)//bfs
{
pp st;
st.x=sx;st.y=sy;
used[sx][sy]=1;
q.push_back(st);
while(!q.empty())
{
pp nw=q.front();
for(int i=0;i<4;i++)
{
pp nxt=nw;
nxt.x+=dx[i];
nxt.y+=dy[i];
if(a[nxt.x][nxt.y]==0 || used[nxt.x][nxt.y]==1) continue;
used[nxt.x][nxt.y]=1;//把这一连通块的点染色
q.push_back(nxt);
}
q.pop_front();
}
}
int main()
{
cin>>n>>m;
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%1d",&a[i][j]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(used[i][j]==0 && a[i][j]!=0)
{
bfs(i,j);
ans++;//若这一连通块没搜过ans++
}
}
}
cout<<ans;
return 0;
}
那 呢 是一次走到底，然后回溯
/*
void dfs()
{
for(拓展状态)
{
判断合法
记录
dfs(继续搜);
回溯;
}
}
*/
所以这题dfs代码
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;
int a[105][105];
bool used[105][105];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
void dfs(int x,int y)
{
used[x][y]=1;
for(int i=0;i<4;i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
if(a[nx][ny]==0 || used[nx][ny]==1) continue;
dfs(nx,ny);
}
}
int main()
{
cin>>n>>m;
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%1d",&a[i][j]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(used[i][j]==0 && a[i][j]!=0)
{
dfs(i,j);
ans++;
}
}
}
cout<<ans;
return 0;
}
其次我们对于区块数量 还有第 种做法 就是我们的并查集
我们可以认为，在某行的数据可表示为（如第一行）
数值：0，2，3，4，5，0，0，0，6，7
位置：1，2，3，4，5，6，7，8，9，10
在[2,5]，[9,10]处有数据
同理，第二行中，[1,1]，[3,6]，[8,8]有数据
你看看
这一行的 [3,6] 与上一行的 [2,5] 有交集，所以他们应该在同一联通块中
#include<cstdio>
int n,m,a[101][101];//a就是地图
int tot=0,fa[10010],stlst/*上一行的起始*/,stnow/*这一行的起始*/,qj[10010][2];
int find(int u)
{
return u==fa[u]?u:fa[u]=find(fa[u]);//板子
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%1d",&a[i][j]);
for(int i=1;(i<<1)<=n*m;i++) fa[i]=i;//最多N*M/2个块
for(int i=1;i<=n;i++)
{
stlst=stnow;
stnow=tot;
for(int j=1;j<=m;j++)
if(a[i][j])
{
qj[tot][0]=j;
while(a[i][j]) j++;
qj[tot][1]=j-1;
for(int k=stlst;k<stnow;k++)
if(qj[k][1]>=qj[tot][0]&&qj[k][0]<=qj[tot][1]) fa[find(k)]=tot;
tot++;
}
}
int ans=0;
for(int i=tot-1;i>=0;i--) if(fa[i]==i)/*我上面没有人*/ ans++;
printf("%d",ans);
}