BFS+优先队列 P1126题解 机器人搬重物

代码自己写了一遍，有几个bug调不出，于是参考了这位大佬的题解：​​​​​​题解 P1126 【机器人搬重物】 - 林则徐 的博客 - 洛谷博客

然后顺利AC了。呜呜呜~先看题目吧！

思路很简单，就是BFS。

需要注意的几个点：

1. 判重：这里我原本只考虑了x,y坐标，但是这样可能会漏解！这边采取的是线性方法。可以使不同的x y direct生成不同的hashr。int hashr(int x,int y,int direct){return direct*2700+x*50+y;}
2. 碰撞检测：机器人走路每走一步都有可能碰到黑块，因此当他在同一方向上走一步遇到阻碍时，就不必走第二第三步了。
3. 要求机器人完成任务所需的最少时间，我用了优先队列，将时间最短的点放在队首。
4. 还有就是方向和转向的数学关系，这点可以大大缩减代码量，减少判断。
   1. case 'N':start.direct=0;break;
      case 'E':start.direct=1;break;
      case 'S':start.direct=2;break;
      case 'W':start.direct=3;break;
   2. int xd[4]={-1,0,1,0};
      int yd[4]={0,1,0,-1};//分别是NESW，与1对应
   3. tmp=(cur.direct+4+1)%4;//右转 tmp=(cur.direct+4-1)%4；//左转

以上是我当时遇到的bug（优先队列可以不用，用不用都能ac）

#include
using namespace std;
#define MAX 55
int n,m;
int g[MAX][MAX];
bool vis[50000]={0};
struct robot{
	int x,y,t,direct;
	//direct=0(north)1(east)2(south)3(west) 
	bool operator < (const robot r)const
	{
		return r.t q;
int xd[4]={-1,0,1,0};
int yd[4]={0,1,0,-1};
int hashr(int x,int y,int direct){return direct*2700+x*50+y;}
//优先队列，每次队首是时间最短的 
int bfs()
{
	while(!q.empty())
	{
		robot cur=q.top();
		//cout<<"出队节点:x="<>n>>m;
	for(int i=0;i>g[i][j];
		}
	}
	char c;
	cin>>start.x>>start.y>>endr.x>>endr.y>>c;
	switch(c)
	{
		case 'N':start.direct=0;break;
		case 'E':start.direct=1;break;
		case 'S':start.direct=2;break;
		case 'W':start.direct=3;break;
	}
	start.t=0;
	q.push(start);
	cout<