题目大意：01矩阵，1表示黑色，0表示白色，求将白色染成黑色最少的次数
使黑色成为一整个联通块。
题解：
搜索bfs 90...
dfs判断连通
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std; int cnt,ans,flag;
int map[][],vis[][];
int mx[]={,,,-},
my[]={,-,,};
string s; struct node{
int x,y;
}a[]; inline void find(int x,int y){
for(int i=;i<;i++){
int xx=x+mx[i],yy=y+my[i];
if(map[xx][yy]&&!vis[xx][yy]){
vis[xx][yy]=true;
find(xx,yy);
}
}
} bool check(){
int gg=;
memset(vis,,sizeof(vis));
for(int i=;i<=;i++)
for(register int j=;j<=;j++)
if(!vis[i][j]&&map[i][j]){
gg++;if(gg>)return false;
vis[i][j]=true;find(i,j);
}
return true;
} void dfs(int x,int sum){
if(x==cnt+){
if(check())
ans=min(ans,sum);
return;
}
map[a[x].x][a[x].y]=;
dfs(x+,sum+);
map[a[x].x][a[x].y]=;
dfs(x+,sum);
} int main(){
for(int i=;i<=;i++){
cin>>s;
for(int j=;j<=;j++){
map[i][j]=s[j-]-'';
if(!map[i][j])a[++cnt].x=i,a[cnt].y=j;
}
}
ans=*;
dfs(,);
printf("%d\n",ans);
return ;
}
90
bfs判断联通
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std; int cnt,ans,flag;
int map[][],vis[][];
int mx[]={,,,-},
my[]={,-,,};
string s; struct node{
int x,y;
}a[];
struct T{
int x,y;
};
queue<T>q; bool check(){
// cout<<"hahahha"<<endl;
flag=false;
memset(vis,,sizeof(vis));
for(int i=;i<=;i++){
for(int j=;j<=;j++){
if(map[i][j]&&!vis[i][j]){
if(flag)return false;
flag=true;
T a;a.x=i;a.y=j;
q.push(a);vis[i][j]=true;
while(!q.empty()){
T now=q.front();q.pop();
int x=now.x,y=now.y;
for(int k=;k<;k++){
int xx=x+mx[k],yy=y+my[k];
if(xx<||yy<||xx>||yy>||vis[xx][yy]||map[xx][yy]!=map[i][j])continue;
T tmp;tmp.x=xx;tmp.y=yy;vis[xx][yy]=true;
q.push(tmp);
}
}
}
}
}
return true;
} void debug(){
for(int i=;i<=;i++){
for(int j=;j<=;j++)
printf("%d",map[i][j]);
printf("\n");
}
cout<<endl<<endl;
}
void dfs(int x,int sum){
if(x==cnt+){
if(check())
ans=min(ans,sum);
return;
}
map[a[x].x][a[x].y]=;
dfs(x+,sum+);
map[a[x].x][a[x].y]=;
dfs(x+,sum);
} int main(){
for(int i=;i<=;i++){
cin>>s;
for(int j=;j<=;j++){
map[i][j]=s[j-]-'';
if(!map[i][j])a[++cnt].x=i,a[cnt].y=j;
}
}
if(cnt==){
printf("0\n");
return ;
}
ans=*;
// debug();
// cout<<endl;
dfs(,);
printf("%d\n",ans);
return ;
}
90
迭代加深搜索
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std; int cnt,ans,flag,ret=-;
int map[][],vis[][];
int mx[]={,,,-},
my[]={,-,,};
string s; struct node{
int x,y;
}a[]; inline void find(int x,int y){
for(int i=;i<;i++){
int xx=x+mx[i],yy=y+my[i];
if(map[xx][yy]&&!vis[xx][yy]){
vis[xx][yy]=true;
find(xx,yy);
}
}
} bool check(){
int gg=;
memset(vis,,sizeof(vis));
for(int i=;i<=;i++)
for(int j=;j<=;j++)
if(!vis[i][j]&&map[i][j]){
gg++;if(gg>)return false;
vis[i][j]=true;find(i,j);
}
return true;
} void dfs(int x,int sum,int deep){
if(ret!=-)return;
if(sum==deep){
if(check())ret=deep;
return;
}
if(x==cnt+)return;//md没有这个一直re
map[a[x].x][a[x].y]=;
dfs(x+,sum+,deep);
map[a[x].x][a[x].y]=;
dfs(x+,sum,deep);
} int main(){
for(int i=;i<=;i++){
cin>>s;
for(int j=;j<=;j++){
map[i][j]=s[j-]-'';
if(!map[i][j])a[++cnt].x=i,a[cnt].y=j;
}
}
if(cnt==){
printf("0\n");
return ;
}
ans=*;
for(int deep=;deep<=;deep++){
dfs(,,deep);
if(ret!=-){
printf("%d\n",ret);
return ;
}
}
return ;
}
AC