洛谷題目鏈接:奶牛美容

題目描述

輸入輸出格式

輸入格式：

輸出格式：

輸入輸出樣例

輸入樣例#1：

6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
..XXX....XXX....

輸出樣例#1：

4

簡述一下題意:給出一個矩陣,矩陣上有三個點(??),要求出最少改變幾個點才能使這三個點變成一個點.

顯然我們可以求出每兩個點的距離,答案就是另外兩個點到這個點的距離之和.

然而這樣是有問題的,比如這樣:

...X.....X... ............. ......X......

這樣這些點并不需要到連同一個點,所以在之前答案的基礎上再枚舉一遍三個點到同一個位置的距離之和能不能更新答案就好了.

步驟:

廣搜求出每個位置所屬的點.

深搜求出一個點到每個位置的最短長度.

對到同一點和三點再外面連通的情況取最小值.

最后答案要-2(因為在計算距離時是算的連入到一個點的長度,所以連進去的那個格子不要算).

#include<bits/stdc++.h> using namespace std; const int N=500+5; const int inf=2147483647;int n, m, cnt = 0, ans = inf; char a[N][N]; int col[N][N]; int mn[N][N]; int d[4][N][N]; int mv[]={1,0,-1,0,1};struct node{int x, y; };bool ok(node nt){if(nt.x < 1 || nt.x > n) return false;if(nt.y < 1 || nt.y > m) return false;if(col[nt.x][nt.y] || a[nt.x][nt.y] != 'X') return false;return true; }void bfs(int x,int y){cnt++; queue <node> q;q.push((node){x,y}); col[x][y] = cnt;node now, nt;while(!q.empty()){now = q.front(); q.pop();for(int i=0;i<4;i++){nt.x = now.x+mv[i]; nt.y = now.y+mv[i+1];if(ok(nt)) col[nt.x][nt.y] = cnt, q.push(nt);}} }void dfs(int color,int x,int y,int step){if(d[color][x][y] <= step) return;d[color][x][y] = step;int nx, ny;for(int i=0;i<4;i++){nx = x+mv[i], ny = y+mv[i+1];if(nx>=1 && nx<=n && ny>=1 && ny<=m)dfs(color,nx,ny,step+1);} }int main(){//freopen("war.in","r",stdin);//freopen("war.out","w",stdout);char ch; cin >> n >> m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin >> a[i][j];for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!col[i][j] && a[i][j] == 'X') bfs(i,j);memset(d,127/3,sizeof(d));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j] == 'X') dfs(col[i][j],i,j,0);memset(mn,127/3,sizeof(mn));for(int c=1;c<=3;c++)for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)mn[col[i][j]][c] = mn[c][col[i][j]] = min(mn[c][col[i][j]],d[c][i][j]);ans = min(mn[1][2]+mn[2][3],min(mn[1][3]+mn[3][2],mn[3][1]+mn[1][2]));for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)ans = min(ans,d[1][i][j]+d[2][i][j]+d[3][i][j]);printf("%d\n",ans-2);return 0; }

轉載于:https://www.cnblogs.com/BCOI/p/8909970.html

總結

以上是生活随笔為你收集整理的[洛谷P2124] 奶牛美容的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。