剛開始看這題的時候覺得就是寬搜+并查集就可以搞定了，覺得一定可以把這題ac的。
然后從昨晚敲代碼，再到今天10點敲到現在，發現有一半樣例WA，實在想不出是什么情況，后來看看錯誤提示，發現橋的數目和長度有可能是不一樣的。欸，那是什么情況呢？突然間覺得好有挫敗感，所以開始研究一份看起來比較簡短優美的題解吧。代碼如下：
#include <algorithm> using namespace std; #define maxn 100000 int xx[8]={0,0,1,1,1,-1,-1,-1},yy[8]={1,-1,0,1,-1,0,1,-1}; int n,m,q[1005][1005],dad[maxn],cnt,ans,sum; bool map[1005][1005]; struct node{int x,y,v;}e[maxn]; //邊的結構體，v代表長度 bool cmp(node a,node b){return a.v<b.v;} int getdad(int x){return x==dad[x]?x:dad[x]=getdad(dad[x]);} //并查集find祖先 bool input(int x1,int y1,int x2,int y2,int t){ if(x2<1||x2>n||y2<1||y2>m||!q[x2][y2]) //坐標不合法或者這不是個建筑物 return 1; //不合法 if(q[x1][y1]==q[x2][y2]) return 0; //屬于同一個建筑物 cnt++; e[cnt].x=q[x1][y1]; e[cnt].y=q[x2][y2]; e[cnt].v=t-1; return 1; } void dfs(int x,int y){ q[x][y]=ans; for(int i=0;i<8;i++){ int x0=x+xx[i],y0=y+yy[i]; if(map[x0][y0]&&!q[x0][y0]) dfs(x0,y0); } } void build(int x,int y) //在(x,y)這個點上可以建的橋 { for(int i=x+1;i<=n;i++) // 下面的 if(!input(x,y,i,y,i-x)||!input(x,y,i,y+1,i-x)||!input(x,y,i,y-1,i-x)) break; for(int i=x-1;i>0;i--) //上面的 if(!input(x,y,i,y,x-i)||!input(x,y,i,y+1,x-i)||!input(x,y,i,y-1,x-i)) break; for(int i=y+1;i<=m;i++) // 右邊的 if(!input(x,y,x,i,i-y)||!input(x,y,x+1,i,i-y)||!input(x,y,x-1,i,i-y)) break; for(int i=y-1;i>0;i--) //左邊的 if(!input(x,y,x,i,y-1)||!input(x,y,x+1,i,y-i)||!input(x,y,x-1,i,y-i)) break; } void work1(){ ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(map[i][j]&&!q[i][j]) {ans++;dfs(i,j);} //ans是聯通塊編號 cout<<ans<<endl; } void work2() { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(map[i][j]) build(i,j); //枚舉所有可能的橋 sort(e+1,e+cnt+1,cmp); //sort所有的橋，長度從小到大 for(int i=1;i<=ans;i++) dad[i]=i;//聯通快編號初始化 ans=0; for(int i=1;i<=cnt;i++) { int k=getdad(e[i].x); int l=getdad(e[i].y); if(k!=l) // 不屬于同一個聯通快，要用橋連接 { dad[k]=l; ans++; sum+=e[i].v; } } cout<<ans<<' '<<sum; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) { char a[maxn]; cin>>a; for(int j=1;j<=m;j++) if(a[j-1]=='#') map[i][j]=1; //整數數組map保存下來了 } work1(); work2(); return 0; }就是枚舉出所有的邊， kruskal+dfs有種力不從心的感覺。但盡量堅持下去吧- -新聞熱點
疑難解答
