本文共 1773 字，大约阅读时间需要 5 分钟。

#include
   
    #include
    
     using namespace std;const int INF = 9999999;const int MAX = 105;struct Node{	int x, y;	int step;};struct cmp{	bool operator () (const Node &a, const Node &b){		return a.step > b.step;	}};struct Pre{	int x, y;	int step;};Pre pre[MAX][MAX];int map[MAX][MAX];int vis[MAX][MAX];char in[MAX];int n, m;int flag;int dir[4][2] = {
  {1,0},{-1,0},{0,1},{0,-1}}; priority_queue
     
      ,cmp> pq;//忘记声明变量了 void bfs()	{		Node start;		start.x = 0; start.y = 0; start.step = 0; 		pq.push(start);		while(!pq.empty()){			Node node = pq.top();			pq.pop();			if(node.x == n-1 && node.y == m-1){				flag = 1;				//cout <<"Hello";				return; 			}			vis[node.x][node.y] = 1;			for(int i = 0; i < 4; i++ ){				int nx = node.x + dir[i][0];				int ny = node.y + dir[i][1];				if(nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny] || map[nx][ny] == -1) continue;				if(map[nx][ny] == 0){					pre[nx][ny].x = node.x; 					pre[nx][ny].y = node.y;					pre[nx][ny].step = node.step;					Node tmp;					tmp.x = nx; tmp.y = ny; tmp.step = node.step + 1;					pq.push(tmp);				}				else{					pre[nx][ny].x = node.x; 					pre[nx][ny].y = node.y;					pre[nx][ny].step = node.step;					Node tmp;					tmp.x = nx; tmp.y = ny; tmp.step = node.step + map[nx][ny] + 1;					pq.push(tmp);				}			}								}					}void printPaht()	{			}	int main()	{//		while(scanf("%d%d",&n,&m) != EOF){//			for(int i = 0; i < n; i++ ){//				scanf("%s",in);//				for(int j = 0; j < m; j++ ){//					if(in[j] == '.'){//						map[i][j] = 0;//					}//					else if(in[j] == 'X'){//						map[i][j] = -1;//					}//					else{//						map[i][j] = in[j]-'0';//					}//					//				}//			}			//			for(int i = 0; i < n; i++ ){//				for(int j = 0; j < m; j++ ){//					printf("%3d",map[i][j]);//				}//				cout <
     
    
   

转载地址：http://qlimi.baihongyu.com/