机器人搬重物

链接

这道题目有方向和体积

我们假设机器人初始坐标为(x,y),那么向东走就是(x,y+1)西(x,y-1)南(x+1,y)北(x-1,y)

那么我们可以设置方向数组

dx[4]={0,1,0,-1}

dy[4]={1,0,-1,0}

当然,由于转向还要时间,我们可以在设置visit二维标记数组的基础上添加方向概念

不妨设东为0,南为1,西为2,北为3

那么,visit就是三维数组了

由于机器人有体积,所以(x,y)到(x+1,y+1)都不能有障碍物

我们在设置一个障碍数组,初始话为0,然后根据四个格子是否有障碍物设为1

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
int n, m;
vector<vector<int>>mp;
vector<vector<int>>can_move;
//E:0 S:1 W:2 N:3
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
bool visit[50][50][4];
struct node {
	int x;
	int y;
	int dir;
	int time;
};
int bfs(int nx,int ny,int ndir,int tx,int ty) {
	queue<node>q;
	q.push({ nx,ny,ndir,0 });
	visit[nx][ny][ndir] = 1;
	while (!q.empty()) {
		node cur = q.front();
		q.pop();
		if (cur.x == tx && cur.y == ty) return cur.time;
		int dir = (cur.dir + 3) % 4;
		if (!visit[cur.x][cur.y][dir]) {
			visit[cur.x][cur.y][dir] = 1;
			q.push({ cur.x,cur.y,dir,cur.time + 1 });
		}
		dir = (cur.dir + 1) % 4;
		if (!visit[cur.x][cur.y][dir]) {
			visit[cur.x][cur.y][dir] = 1;
			q.push({ cur.x,cur.y,dir,cur.time + 1 });
		}
		for (int step = 1;step <= 3;step++) {
			int x = cur.x + dx[cur.dir] * step;
			int y = cur.y + dy[cur.dir] * step;
			bool ok = true;
			for (int k = 1;k <= step;k++) {
				int cx = cur.x + dx[cur.dir] * k;
				int cy = cur.y + dy[cur.dir] * k;
				if (cx<0||cx>=n-1||cy<0||cy>=m-1||!can_move[cx][cy]) {
					ok = 0;	
					break;
				}
			}
			if (!ok) break;
			if (!visit[x][y][cur.dir]) {
				visit[x][y][cur.dir] = 1;
				q.push({ x,y,cur.dir,cur.time + 1 });
			}
		}
	}
	return -1;
}
int main() {
	cin >> n >> m;
	mp.resize(n, vector<int>(m));
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			cin >> mp[i][j];
		}
	}
	can_move.resize(n, vector<int>(m, 0));
	for (int i = 0;i < n - 1;i++) {
		for (int j = 0;j < m - 1;j++) {
			if (!mp[i][j] && !mp[i + 1][j] && !mp[i][j + 1] && !mp[i + 1][j + 1]) {
				can_move[i][j] = 1;
			}
		}
	}
	memset(visit, 0, sizeof(visit));
	int nx, ny, tx, ty;
	cin >> nx >> ny >> tx >> ty;
	int dir = 0;
	char Dir;
	cin >> Dir;
	if (Dir == 'E') dir = 0;
	else if (Dir == 'S') dir = 1;
	else if (Dir == 'W') dir = 2;
	else dir = 3;
	if (nx < 1 || nx >= n || ny < 1 || ny >= m  || !can_move[nx-1][ny-1]) {
		cout << -1 << endl;
		return 0;
	}
	if (tx < 1 || tx >= n  || ty < 1 || ty >= m  || !can_move[tx-1][ty-1]) {
		cout << -1 << endl;
		return 0;
	}
	cout << bfs(nx-1, ny-1, dir, tx-1, ty-1);
}

时间复杂度:O(nm)

空间复杂度:O(nm)