题意：求从开始点到目标点的最小的能量消耗，如果下一格的风向和当前的一样的话，消耗为0，否则为1，一共8个方向，其实方向是0
思路：BFS的基础上还要加上优先队列来取能量的最小值
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 1010;
const int INF = 0x3f3f3f3f;
struct node{
int x,y,c;
bool operator <(const node &a)const{
return c > a.c;
}
}tmp;
int n,m,sx,sy,ex,ey;
char map[MAXN][MAXN];
int f[MAXN][MAXN];
int dir[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
void bfs(){
priority_queue<node> q;
node a = {sx,sy,0};
q.push(a);
while (!q.empty()){
tmp = q.top();
q.pop();
int tx = tmp.x,ty = tmp.y;
if (tx == ex && ty == ey)
return;
int cost;
for (int i = 0; i < 8; i++){
tx = tmp.x + dir[i][0];
ty = tmp.y + dir[i][1];
if (tx >= 0 && tx < n && ty >= 0 && ty < m){
int d = (map[tmp.x][tmp.y]-‘0‘);
if (i == d)
cost = tmp.c;
else cost = tmp.c + 1;
node cur = {tx,ty,cost};
if (f[tx][ty] > cost){
f[tx][ty] = cost;
q.push(cur);
}
}
}
}
}
int main(){
while (scanf("%d%d",&n,&m) != EOF){
for (int i = 0; i < n; i++)
scanf("%s",map[i]);
int t;
scanf("%d",&t);
while (t--){
for (int i = 0; i <= n; i++)
for (int j = 0; j <= m; j++)
f[i][j] = INF;
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
sx--,sy--,ex--,ey--;
f[sx][sy] = 0;
bfs();
printf("%d\n",f[ex][ey]);
}
}
return 0;
}HDU - 2757 Ocean Currents （BFS+优先队列）,布布扣,bubuko.com
HDU - 2757 Ocean Currents （BFS+优先队列）
原文：http://blog.csdn.net/u011345136/article/details/21335261