题目地址：http://poj.org/problem?id=1376
纯属为了练习A*而写的
实际上A*感觉并不怎么占优势，因为转向不知道怎么体现在估价函数h()上，我只是用了曼哈顿距离当作h()
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=50+5;
int R,C,r0,c0,t0,r,c;
struct Node{int x,y; int f,g,h;int toward;Node(int x,int y,int g,int h,int t):x(x),y(y),f(g+h),g(g),h(h),toward(t){}bool operator < (const Node& n) const {if(g==n.g) return f>n.f;return g>n.g; //因为转向并未考虑到h函数中，所以以f比并不准确 }
};
bool closed[maxn][maxn][4];
int G[maxn][maxn];
int H(int x,int y){return abs(x-r)+abs(y-c); //h()函数只考虑了位置
}
const int dx[]={-1,0,1,0}; //up right down left
const int dy[]={0,1,0,-1};
bool inside(int x,int y){return x>0&&y>0&&x<R&&y<C; //不能到边界
}
int A_Star()
{if(G[r][c]) return -1; //当终点是1时肯定不行 memset(closed,false,sizeof(closed));priority_queue<Node> open;open.push(Node(r0,c0,0,H(r0,c0),t0));closed[r0][c0][t0]=true;while(!open.empty()){int x=open.top().x, y=open.top().y, g=open.top().g, h=open.top().h, t=open.top().toward;open.pop();if(x==r&&y==c) return g;for(int i=1;i<=3;i++) { //go straight int nx=x+dx[t]*i;int ny=y+dy[t]*i;if(!inside(nx,ny)||G[nx][ny]) break;if(closed[nx][ny][t]) continue;open.push(Node(nx,ny,g+1,H(nx,ny),t));closed[nx][ny][t]=true; } //即时放入closed，更加省空间 ，不然会MLE int nt=(t-1+4)%4; //turn rightif(!closed[x][y][nt]) open.push(Node(x,y,g+1,h,nt)),closed[x][y][nt]=true;nt=(t+1)%4; //turn leftif(!closed[x][y][nt]) open.push(Node(x,y,g+1,h,nt)),closed[x][y][nt]=true;}return -1;
}
int main()
{char t[]="nesw";string s;while(cin>>R>>C){if(R==0&&C==0) break; memset(G,0,sizeof(G));for(int i=1;i<=R;i++)for(int j=1;j<=C;j++){cin>>G[i][j];if(G[i][j]) G[i-1][j]=G[i][j-1]=G[i-1][j-1]=1;} cin>>r0>>c0>>r>>c>>s;t0=find(t,t+5,s[0])-t;cout<<A_Star()<<endl;}return 0;
}