Problem?Description
Pass?a?year?learning?in?Hangzhou,?yifenfei?arrival?hometown?Ningbo?at?finally.?Leave?Ningbo?one?year,?yifenfei?have?many?people?to?meet.?Especially?a?good?friend?Merceki.
Yifenfei’s?home?is?at?the?countryside,?but?Merceki’s?home?is?in?the?center?of?city.?So?yifenfei?made?arrangements?with?Merceki?to?meet?at?a?KFC.?There?are?many?KFC?in?Ningbo,?they?want?to?choose?one?that?let?the?total?time?to?it?be?most?smallest.?
Now?give?you?a?Ningbo?map,?Both?yifenfei?and?Merceki?can?move?up,?down?,left,?right?to?the?adjacent?road?by?cost?11?minutes.
Yifenfei’s?home?is?at?the?countryside,?but?Merceki’s?home?is?in?the?center?of?city.?So?yifenfei?made?arrangements?with?Merceki?to?meet?at?a?KFC.?There?are?many?KFC?in?Ningbo,?they?want?to?choose?one?that?let?the?total?time?to?it?be?most?smallest.?
Now?give?you?a?Ningbo?map,?Both?yifenfei?and?Merceki?can?move?up,?down?,left,?right?to?the?adjacent?road?by?cost?11?minutes.
?
Input
The?input?contains?multiple?test?cases.
Each?test?case?include,?first?two?integers?n,?m.?(2<=n,m<=200).?
Next?n?lines,?each?line?included?m?character.
‘Y’?express?yifenfei?initial?position.
‘M’????express?Merceki?initial?position.
‘#’?forbid?road;
‘.’?Road.
‘@’?KCF
Each?test?case?include,?first?two?integers?n,?m.?(2<=n,m<=200).?
Next?n?lines,?each?line?included?m?character.
‘Y’?express?yifenfei?initial?position.
‘M’????express?Merceki?initial?position.
‘#’?forbid?road;
‘.’?Road.
‘@’?KCF
Output
For?each?test?case?output?the?minimum?total?time?that?both?yifenfei?and?Merceki?to?arrival?one?of?KFC.You?may?sure?there?is?always?have?a?KFC?that?can?let?them?meet.
Sample?Input
4?4?
Y.#@
....?
.#..
@..M?
4?4
Y.#@
....
.#..?
@#.M?
5?5?
Y..@
.?.#.
..?.#
...?@
..M.?
#...#
?
Sample?Output
66
88
66
哈哈，這是第一次自己做廣搜的題目，wrong?answer?-?超時??這就是大半天。?
犯得主要錯誤:
1、沒有對連個隊列訪問的點進行標記，導致重復訪問。
2、總覺得廣搜首先搜出來的相遇地點就是最短的。
?????我同學一句話就把我點醒了，首先搜出來的是Y?M兩個距離相差最小的相遇地點，卻不是距離和最小的。
??????所以，最后還要找出距離和最小的那個相遇地點。
?
View Code 1 #include<iostream> 2 #include<queue> 3 #define inf 0x7f7f7f7f7f 4 using namespace std; 5 6 char map[210][210]; 7 typedef struct 8 { 9 int x ,y; 10 int step; 11 }node; 12 int vis_Y[210][210]; 13 int vis_M[210][210]; 14 int vis[210][210]; 15 int end_step[210][210]; 16 int dx[4] = {0,1,0,-1}; 17 int dy[4] = {1,0,-1,0}; 18 int n , m; 19 20 int bfs(node &temp , int i , int flag) 21 { 22 temp.x += dx[i]; 23 temp.y += dy[i]; 24 if(temp.x<0||temp.x>=n||temp.y<0||temp.y>=m) return 0; //越界 25 if(flag) 26 if(vis_Y[temp.x][temp.y]) return 0; //已經訪問 27 if(!flag) 28 if(vis_M[temp.x][temp.y]) return 0; //已經訪問 29 if(map[temp.x][temp.y] == '#') return 0; 30 else if(map[temp.x][temp.y] == '.') 31 { 32 if(flag) vis_Y[temp.x][temp.y] = 1; 33 else vis_M[temp.x][temp.y] = 1; 34 } 35 else if(map[temp.x][temp.y] == '@') 36 { 37 if(flag) vis_Y[temp.x][temp.y] = 1; 38 else vis_M[temp.x][temp.y] = 1; 39 vis[temp.x][temp.y]++; 40 end_step[temp.x][temp.y] += temp.step+1; 41 } 42 temp.step++; 43 return 1; 44 } 45 int main() 46 { 47 int i , j , min; 48 while(cin>>n>>m) 49 { 50 memset(vis_Y , 0 , sizeof(vis_Y)); 51 memset(vis_M , 0 , sizeof(vis_M)); 52 memset(vis , 0 , sizeof(vis)); 53 memset(end_step , 0 , sizeof(end_step)); 54 min = inf; 55 queue<node>q_Y; 56 queue<node>q_M; 57 node start_Y , start_M; 58 for(i = 0; i < n; i++) 59 { 60 getchar(); 61 for(j = 0; j < m; j++) 62 { 63 scanf("%c" , &map[i][j]); 64 if(map[i][j] == 'Y') 65 {start_Y.x = i; start_Y.y = j; start_Y.step = 0; vis_Y[i][j] = 1;} 66 else if(map[i][j] == 'M') 67 {start_M.x = i; start_M.y = j; start_M.step = 0; vis_M[i][j] = 1;} 68 } 69 map[i][j] = '\0'; 70 } 71 q_Y.push(start_Y); 72 q_M.push(start_M); 73 while(!q_Y.empty() && !q_M.empty()) 74 { 75 int flag = 0; 76 node temp1 = q_Y.front(); 77 node temp2 = q_M.front(); 78 q_Y.pop(); q_M.pop(); 79 for(i = 0; i < 4; i++) 80 { 81 node temp3 = temp1; 82 node temp4 = temp2; 83 if(bfs(temp3 , i , 1)) 84 q_Y.push(temp3); 85 if(bfs(temp4 , i , 0)) 86 q_M.push(temp4); 87 } 88 } 89 for(i = 0; i < n; i++) 90 for(j = 0; j < m; j++) 91 if(vis[i][j] == 2) 92 { 93 if(min > end_step[i][j]) 94 min = end_step[i][j]; 95 } 96 cout<<min*11<<endl; 97 } 98 return 0; 99 }
?
)
