我的思路过于麻烦，是先用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 ; }
