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

liuchengxu 发布于2021-09-02 15:40 / 1778人阅读

摘要：机器人搬重物传送门这道题本来没啥好说的，但细节实在比较多，被坑了好多次。

P1126 机器人搬重物

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

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

代码：

#include #define MAX 55using 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;}

超融合服务器混合云题解 oj题解搬瓦工搬瓦工

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/118867.html

大学一年之后竟如此。。。开学前的挣扎

摘要：后来知道有了院赛，学长说刷院和杭电就可，我就一直刷院，到最后比赛前院的前五十道基本做完，杭电也弄了十来道，就这样草草参加比赛了。博客主页: https://b...

MartinDai 2021-09-06 15:02 评论0 收藏0
从编程到养生编程

摘要：年月日，正式开始了前端编程生涯，距今恰好一年。关注的话题却不再是纯粹的编程，而是从编程变成了养生编程，毕竟生活不能只有代码，还有健康家庭和未来。编程本就是份高危行业，的风波影响至今犹在。2018 年 5 月 2 日，jsliang 正式开始了前端编程生涯，距今恰好一年。关注的话题却不再是纯粹的编程，而是从编程变成了养生编程，毕竟生活不能只有代码，还有健康、家庭和未来。一目录目录...

Java3y 2019-05-23 17:32 评论0 收藏0
LuxTdmZtIC

摘要：转载史上最简单的平衡树无旋作者博客地址使用此文件时请保留上述信息谢谢合作觉得文章不错请点击链接为博客点赞高能预警所有示例代码都是数组版的欢迎前置知识线段树请确保你完全理解最基础的线段树和区间加法和区间求和一简介无旋又称是范浩强大佬发明的一种【转载】史上最简单的平衡树——无旋Treap showImg(https://segmentfault.com/img/bVbuWGu?w=60...

CoffeX 2019-08-02 15:24 评论0 收藏0
LuxTdmZtIC

摘要：转载史上最简单的平衡树无旋作者博客地址使用此文件时请保留上述信息谢谢合作觉得文章不错请点击链接为博客点赞高能预警所有示例代码都是数组版的欢迎前置知识线段树请确保你完全理解最基础的线段树和区间加法和区间求和一简介无旋又称是范浩强大佬发明的一种【转载】史上最简单的平衡树——无旋Treap showImg(https://segmentfault.com/img/bVbuWGu?w=60...

tuantuan 2019-08-23 18:22 评论0 收藏0
LuxTdmZtIC

摘要：转载史上最简单的平衡树无旋作者博客地址使用此文件时请保留上述信息谢谢合作觉得文章不错请点击链接为博客点赞高能预警所有示例代码都是数组版的欢迎前置知识线段树请确保你完全理解最基础的线段树和区间加法和区间求和一简介无旋又称是范浩强大佬发明的一种【转载】史上最简单的平衡树——无旋Treap showImg(https://segmentfault.com/img/bVbuWGu?w=60...

roundstones 2019-08-30 11:17 评论0 收藏0