acwing 2060 奶牛选美

简介: acwing 2060 奶牛选美

2060. 奶牛选美 - AcWing题库

我的思路过于麻烦,是先用dfs搜索其中一个联通块,选出来以后对他进行,连通性的判断, 把这个连通块全部标记为1,然后我们从每一个1出发进行bfs , 当走到一个点,我们就判断一下是否走过这个点,和这个点以前的距离是否比我们现在走到这里的距离远,如果要远的话我们就要更新一下距离;

最后bfs处理完全图以后我们需要对dfs找第二个联通块, 然后找连通块中距离最少的那个值

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std ;
const int N = 100 , INF = 1e9 ;
char mp[N][N] ;
int d[4][2] = {{0,1},{0,-1},{1,0},{-1,0}} ;
int n , m ;
int qx,qy ;
 
struct node{
  int x, y ;
  node(int xx , int yy ){
    x = xx , y = yy  ;
  }
};
queue<node> q ;
int f[N][N] ;
vector<node> a ;
void dfs1(int x , int y){//染色 
  mp[x][y] = '1' ;
  a.push_back(node(x,y)) ;
  for(int i =0 ; i < 4 ; i ++){
    int tx = x + d[i][0] , ty = y + d[i][1] ;
    if(tx<0||tx>=n||ty<0||ty>=m) continue ;
    if(mp[tx][ty] == '1' || mp[tx][ty] == '.') continue ;
    if(mp[tx][ty] == 'X') dfs1(tx,ty) ;
  }
}
void bfs(int x,int y ){
  q.push(node(x,y)) ;
  while(!q.empty()){
    node now= q.front() ;
    q.pop() ;
    int dx = now.x , dy = now.y ;
    for(int i = 0 ; i < 4 ; i ++){
      int tx = dx + d[i][0] , ty = dy + d[i][1] ;
      
      if(tx<0||tx>=n||ty<0||ty>=m||mp[tx][ty] == '1') continue ;
      
      if(f[tx][ty] > f[dx][dy] + 1){
        f[tx][ty] = f[dx][dy] + 1 ;
        q.push(node(tx,ty)) ;
      }
      else continue ;
      
    }
    
  }
}
 
int main(){
  cin >> n >> m ;
  for(int i = 0 ; i < n ; i ++)
    for(int j = 0  ;j < m ; j ++) cin >> mp[i][j] ;
    
  for(int i = 0 ; i < n;i++){
    for(int j = 0 ; j < m ; j ++){
      if(mp[i][j] == 'X') qx = i , qy = j ;
    }
  }
  for(int i = 0 ; i < n;i++){
    for(int j = 0 ; j < m ; j ++){
      f[i][j] = INF-10000 ;
    }
  }
//  for(int i = 0 ; i < n;i++){
//    for(int j = 0 ; j < m ; j ++){
//      cout << f[i][j] << " " ;
//    }
//    cout << endl ;
//  }
  dfs1(qx,qy) ;
  //int cnt = a.size() ; cout << cnt << endl ;
  for(int i = 0 ; i < a.size() ; i++){
    int x = a[i].x , y = a[i].y;
    f[x][y] = 0 ;
    bfs(x,y) ;
  }
//  for(int i = 0 ; i < n;i++){
//    for(int j = 0 ; j < m ; j ++){
//      cout << f[i][j] << " " ;
//    }
//    cout << endl ;
//  }
  for(int i = 0 ; i < n;i++){
    for(int j = 0 ; j < m ; j ++){
      if(mp[i][j] == 'X') qx = i , qy = j ;
    }
  }
  a.clear() ;
  dfs1(qx,qy) ;
  int res = INF ;
 
  for(int i = 0 ; i < a.size(); i ++){
    int x = a[i].x , y = a[i].y ;
    res = min(f[x][y],res) ;
  }
  cout << res -1<< endl ;
}
目录
相关文章
|
2月前
lanqiao OJ 1447 砝码称重
lanqiao OJ 1447 砝码称重
30 1
|
2月前
lanqiao OJ 1505 剪邮票
lanqiao OJ 1505 剪邮票
27 0
|
2月前
acwing 1106 山峰和山谷
acwing 1106 山峰和山谷
11 0
|
2月前
acwing 1098 城堡
acwing 1098 城堡
13 0
|
2月前
acwing 1113 红与黑
acwing 1113 红与黑
10 0
|
2月前
lanqiao OJ 2097 青蛙过河
lanqiao OJ 2097 青蛙过河
11 0
AcWing 2060. 奶牛选美(每日一题)
AcWing 2060. 奶牛选美(每日一题)
|
5月前
|
人工智能
【洛谷】P2678 跳石头
洛谷 P2678 跳石头
37 0
【洛谷】P2678 跳石头
|
存储 算法 Java
【AcWing每日一题】4818. 奶牛大学
【AcWing每日一题】4818. 奶牛大学
119 0
《蓝桥杯每日一题》递推·AcWing 3777. 砖块
《蓝桥杯每日一题》递推·AcWing 3777. 砖块
80 0