题目链接 http://acm.dhu.edu.cn/contest/view.html?id=875&index=1
优先队列，步数相同的，*号优先
#include<stdio.h> #include<time.h> #include<cmath> #include <iostream> #include<string.h> #include <set> #include <queue> using namespace std; typedef long long ll; const int maxn = 21; char a[55][55]; class Node{ public : int x;int y;int d; Node(int a, int b, int c):x(a),y(b),d(c){} }; bool operator < (const Node &t1, const Node&t2) { return t1.d > t2.d||(t1.d==t2.d&&((a[t1.x][t1.y]==a[t2.x][t2.y])||(a[t1.x][t1.y]=='#'&&a[t2.x][t2.y]=='*'))); // 按照z的顺序来决定t1和t2的顺序 } int dx[4]={-1,0,1,0}; int dy[4]={0,-1,0,1}; int res[55][55]; int main() { int n; priority_queue<Node> q; while(scanf("%d",&n)!=EOF){ memset(res, 0, sizeof(res)); // cout<<n<<endl; while(!q.empty()){ q.pop(); } for(int i=0;i<n;i++) for(int j=0;j<n;j++){ cin>>a[i][j]; } // for(int i=0;i<n;i++) // for(int j=0;j<n;j++){ // cout<<a[i][j]; // } q.push(Node(0,0,0)); res[0][0] = 1; int tx,ty,td; while (!q.empty()){ Node t = q.top(); q.pop(); // cout<<t.x<<" "<<t.y<<" "<<t.d<<endl; if(t.x==n-1&&t.y==n-1){ cout<<t.d<<endl;break; } for(int i=0;i<4;i++){ tx = t.x+dx[i]; ty = t.y+dy[i]; td = t.d; if(res[tx][ty]==0&&tx>=0&&ty>=0&&tx<n&&ty<n){ res[tx][ty]=1; if(a[t.x][t.y]=='#'||a[tx][ty]=='#') td++; q.push(Node(tx,ty,td)); // cout<<tx<<" "<<ty<<" "<<td<<endl; } } } } return 0; }