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