P1126 机器人搬重物（C++_BFS）

题目描述

机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径1.6米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个N×M 的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：向前移动1步（Creep）；向前移动2步（Walk）；向前移动3 步（Run）；向左转（Left）；向右转（Right）。每个指令所需要的时间为1 秒。请你计算一下机器人完成任务所需的最少时间。

输入格式

第一行为两个正整数N,M(N,M≤50)，下面N行是储藏室的构造，0表示无障碍，1表示有障碍，数字之间用一个空格隔开。接着一行有4个整数和1个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东E，南S，西W，北N），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。

输出格式

一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出−1。

输入输出样例

输入 #1

9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 S

输出 #1

12

反思

这个sb题，我思路完全ok就是不给过，硬生生卡了好久，最后还非要我把代码改的和别人差不多才过。

源码

#include<bits/stdc++.h>
using namespace std;
int n, m;
int s[60][60];//储物室构造
int cf[60][60][4] = { 0 };//判重
int a[4] = { -1,0,1,0 };
int b[4] = { 0,1,0,-1 };
class node
{
public:
	int x = 0, y = 0;
	int dir;//N-0,E-1,S-2,W-3
	int time = 0;
};
node beginn, endd;
queue<node> r;
bool limit(int xx, int yy)//障碍物
{
	if (s[xx][yy]|| s[xx + 1][yy]|| s[xx][yy + 1]|| s[xx + 1][yy + 1])
		return true;
	return false;
}
void bfs()
{
	node temp;
	r.push(beginn);
	while (!r.empty())
	{
		temp = r.front();
		r.pop();
		int t_x = temp.x;
		int t_y = temp.y;
		int dir = temp.dir;
		if (temp.x == endd.x && temp.y == endd.y)
		{
			cout << temp.time;
			exit(0);
		}
		if (cf[temp.x][temp.y][temp.dir] == 1)
			continue;
		cf[temp.x][temp.y][temp.dir] = 1;//查重
		temp.time++;
		temp.dir = (dir + 3) % 4;
		r.push(temp);
		temp.dir = (dir + 5) % 4;
		r.push(temp);
		temp.dir = dir;
		for (int j = 1; j <= 3; j++)//三种速度
		{
			int temp_x = t_x + a[dir] * j;//移动
			int temp_y = t_y + b[dir] * j;
			if (temp_x <= 0 || temp_x >= n || temp_y <= 0 || temp_y >= m || limit(temp_x, temp_y))//判定可否移动以及边界
				break;
			temp.x = temp_x;
			temp.y = temp_y;
			r.push(temp);
		}
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> s[i][j];
	cin >> beginn.x >> beginn.y;
	cin >> endd.x >> endd.y;
	char temp;
	cin >> temp;
	if (temp == 'N')
		beginn.dir = 0;
	else if (temp == 'S')
		beginn.dir = 2;
	else if (temp == 'E')
		beginn.dir = 1;
	else if (temp == 'W')
		beginn.dir = 3;
	bfs();
	cout << -1;
	return 0;
}