要求在圖中找出距離最遠的兩個點的距離。 這題暴力枚舉每一點出發的最長路徑顯然不可行。 從任意點A出發的最長路徑的另一個端點稱為B，那麼B就是全局最長路徑的一個端點。那麼，從B點開始一次廣搜，到達的最遠點叫C。BC即是圖中的最長路徑。 [cpp] #include <iostream> #include <math.h> #include <stdio.h> #include <string.h> #include <queue> #include <algorithm> #include <stack> using namespace std; int column,row; int map[1002][1002]; int dis[1002][1002]; int disx[4] = {0,1,0,-1}; int disy[4] = {1,0,-1,0}; int maxX; int maxY; struct Point { int x; int y; }; int bfs(int startx,int starty) { queue<Point> p; Point nex,temp; maxX = startx; maxY = starty; int maxP = 0; nex.x = startx; nex.y = starty; p.push(nex); while(!p.empty()) { temp = p.front(); p.pop(); for(int i=0; i<4; i++) { int tempx = temp.x + disx[i]; int tempy = temp.y + disy[i]; if(tempx>=0 && tempx<row && tempy>=0 && tempy<column) { if(map[tempx][tempy] == 1) { map[tempx][tempy] = 2; dis[tempx][tempy] += dis[temp.x][temp.y] + 1; nex.x = tempx; nex.y = tempy; p.push(nex); if(dis[tempx][tempy]>maxP) { maxP = dis[tempx][tempy]; maxX = tempx; maxY = tempy; } } } } } return maxP; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif int t; char c; scanf(" %d ",&t); int startx,starty; while(t--) { memset(map,0,sizeof(map)); memset(dis,0,sizeof(dis)); scanf(" %d %d ",&column,&row); for(int i=0; i<row; i++) { for(int j=0; j<column; j++) { scanf(" %c ",&c); if(c == '.') { map[i][j] = 1; } } } for(int i=0; i<row; i++) { int flag = 0; for(int j=0; j<column; j++) { if(map[i][j] == 1) { flag = 1; startx = i; starty = j; break; } } if(flag == 1) { break; } } map[startx][starty] = 2;//標記為已訪問過 bfs(startx,starty); //還原原map for(int i=0; i<row; i++) { www.2cto.com for(int j=0; j<column; j++) { if(map[i][j] == 2) { map[i][j] = 1; } } } memset(dis,0,sizeof(dis)); printf("Maximum rope length is %d.\n",bfs(maxX,maxY)); } return 0; }
