华南中天论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
热搜: 活动 交友 discuz
华南中天论坛 门户 网络技术 基础技术 查看内容

【题解】【洛谷P1126】 机器人搬重物

2020-1-14 23:48| 发布者: 山村学生| 查看: 88| 评论: 0

摘要: P1126 机器人搬重物 传送门 这道题本来没啥好说的,但细节实在比较多,被坑了好多次。 首先输入的是格子图,需要转化成点图,具体操作是 最坑的一个点在于,平时写宽搜的时候,遇到出边界或者不能访问的点时,都

P1126 机器人搬重物

传送门


这道题本来没啥好说的,但细节实在比较多,被坑了好多次。

  1. 首先输入的是格子图,需要转化成点图,具体操作是
    a[i][j]=a[i-1][j-1]=a[i][j-1]=a[i-1][j]=1
  2. 最坑的一个点在于,平时写宽搜的时候,遇到出边界或者不能访问的点时,都是直接进入下一层循环(continue),但在这道题中,由于可以走1~3步,那么当路径上出现障碍时,则不能进行下一轮循环,需要break。

代码:

#include 
#define MAX 55
using namespace std;

int mod(int x){
	return (x+4)%4;
}

struct pt{
	int x, y, dir, step;
	pt(){}
	pt(int a, int b, int c, int d):x(a), y(b), dir(c), step(d){}
};

const int movx[] = {0,1,0,-1}, movy[] = {1,0,-1,0};
int a[MAX][MAX];
bool vis[MAX][MAX][5];
int n, m;
pt st, ed;

void bfs(){
	queue q;
	bool flag = false;
	st.step = 0;
	q.push(st);
	vis[st.x][st.y][st.dir] = true;
	while(!q.empty()){
		pt t = q.front();
		q.pop();
		if(t.x == ed.x && t.y == ed.y){
			cout << t.step << endl;
			flag = true;
			break;
		}
		for(int i = 1; i <= 3; i++){
			int u, v;
			u = t.x + i*movx[t.dir];
			v = t.y + i*movy[t.dir];
			if(u<=0 || u>=n || v<=0 || v>=m || a[u][v] == 1){
				break;
			}
			if(vis[u][v][t.dir]){
				continue;
			}
			vis[u][v][t.dir] = true;
			q.push(pt(u, v, t.dir, t.step+1));
		}
		if(!vis[t.x][t.y][mod(t.dir+1)]){
			vis[t.x][t.y][mod(t.dir+1)] = true;
			q.push(pt(t.x, t.y, mod(t.dir+1), t.step+1));
		}
		if(!vis[t.x][t.y][mod(t.dir-1)]){
			vis[t.x][t.y][mod(t.dir-1)] = true;
			q.push(pt(t.x, t.y, mod(t.dir-1), t.step+1));
		}
	}
	if(!flag){
		cout << -1 << endl;
	}
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			scanf("%d", &a[i][j]);
			if(a[i][j] == 1){
				a[i-1][j-1] = a[i-1][j] = a[i][j-1] = 1;
			}
		}
	}
	cin >> st.x >> st.y >> ed.x >> ed.y;
	char c;
	cin >> c;
	switch(c){
		case 'E':
			st.dir = 0; break;
		case 'S':
			st.dir = 1; break;
		case 'W':
			st.dir = 2; break;
		case 'N':
			st.dir = 3; break;
	}
	bfs();
	
	return 0;
}

 

JokerJim 发布了62 篇原创文章 · 获赞 21 · 访问量 3万+ 私信 关注
来源:https://blog.csdn.net/qq_30115697/article/details/85987667
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

鲜花

握手

雷人

路过

鸡蛋

最新评论

QQ|Archiver|手机版|小黑屋|南华中天社区 ( 粤ICP备11019662号 )

GMT+8, 2020-11-24 12:19 , Processed in 0.032745 second(s), 15 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

返回顶部