http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1301
就是普通的广度优先搜索，不过需要在搜索的过程中记录状态，数据结构写起来稍微麻烦一点儿。WA好多次，一直没找到原因，非常郁闷。由于马上要用到了，就又检查了几遍，还是没找到哪儿错了。最后实在没办法了把队列由1000改为2000就过了！！！郁闷！！！已经有好几次倒在数组开得太小上了！！！以后一定要开大点儿。
下面是源代码，写的不好，有时间会改进一下的。
#include<iostream>#include<string>using namespace std;
struct Queue{ int x,y,father; int step,index; char method; };Queue queue[1000],game_end;char board[20][20],output_array[1000];int n,queue_start,queue_end,start_x,start_y,end_x,end_y,r,c,game_is_end,sum;int dx[4] = {1,-1,0,0},dy[4] = {0,0,1,-1};void walk();void output();int main(){ sum = 0; int i,j,k; char temp; while(cin>>r>>c) { game_is_end = 0; queue_start = 0; queue_end = 0; for (i = 0;i < r;i++) { for (j = 0;j < c;j++) { cin>>temp; board[i][j] = temp; if(temp == 'S') { start_x = i; start_y = j; } else if (temp == 'E') { end_x = i; end_y = j; } } } walk(); } return 0;}
void walk(){ int i,j,k,temp_i,temp_j; Queue temp_node; queue[queue_end].x = start_x; queue[queue_end].y = start_y; queue[queue_end].father = -1; queue[queue_end].step = 0; queue[queue_end].index = 0; queue_end++; while(queue_start < queue_end && !game_is_end ) { temp_node = queue[queue_start]; queue_start++; for (i = 0;i < 4;i++) { temp_i = temp_node.x; temp_j = temp_node.y; while(board[temp_i][temp_j] != '#' && temp_i >=0 && temp_i < r && temp_j >= 0 && temp_j < c && !game_is_end) { if (temp_i == end_x && temp_j == end_y) { game_is_end = 1; game_end.x = temp_i; game_end.y = temp_j; game_end.father = temp_node.index; game_end.step = temp_node.step + 1; game_end.index = queue_end; queue_end++; switch(i) { case 0: game_end.method = 'd';break; case 1: game_end.method = 'u';break; case 2: game_end.method = 'r';break; case 3: game_end.method = 'l';break; } output(); break; } temp_i = temp_i + dx[i]; temp_j = temp_j + dy[i]; } if (board[temp_i][temp_j] == '#' && temp_i >=0 && temp_i < r && temp_j >= 0 && temp_j < c && !game_is_end) { if (!((temp_i == temp_node.x + dx[i]) && (temp_j == temp_node.y + dy[i]))) { temp_i -= dx[i]; temp_j -= dy[i]; queue[queue_end].father = temp_node.index; queue[queue_end].step = temp_node.step +1; queue[queue_end].index = queue_end; queue[queue_end].x = temp_i; queue[queue_end].y = temp_j; switch(i) { case 0: queue[queue_end].method = 'd';break; case 1: queue[queue_end].method = 'u';break; case 2: queue[queue_end].method = 'r';break; case 3: queue[queue_end].method = 'l';break; } queue_end++; } } } }}
void output(){ Queue temp_queue_node; int i,j,k; i = game_end.father; temp_queue_node = game_end; cout<<"Case "<<++sum<<":"<<endl; cout<<game_end.step<<endl; j = game_end.step; while(j) { output_array[j-1] = temp_queue_node.method; i = temp_queue_node.father; temp_queue_node = queue[i]; j--; } j = game_end.step; for(k = 0;k < j;k++) { cout<<output_array[k]; } cout<<endl; }
转载于:https://www.cnblogs.com/xinguohenan/archive/2009/05/26/1489344.html
相关资源：各显卡算力对照表！