计算机视觉技术 开源商城系统 session vue例子 管理后台框架 安卓项目实战 nginx视频 short几个字节 js数组截取前5个 python转java hbuilder插件 mysql新建数据库 python的extend eclipse安装python python返回值 java中的多态 java正则表达式用法 java中new java怎么配置环境变量 java新建文件 java版本查看 java删除目录 java怎么编程 java读文件 java文件输入输出 linux用户 php网络编程 js绝对值 免费脚本 免费书籍 魔兽地图七个人 苹果手机总是自动重启 压枪软件 小米游戏鼠标 正则表达式数字 剑灵龙骨卷轴 德玛上单天赋 召唤加点90刷图加点 水之td合成 ppt背景音乐怎么关
当前位置: 首页 > 学习教程  > 编程语言

【蓝桥杯第十届省赛A组】试题D: 迷宫

2020/10/16 17:58:01 文章标签:

一看到题目用最短的路径,首先想到要用BFS,其次,要求记录路径,我们可以在状态里面添加字符串变量(也即我的代码里面的ans,每到达一个地点字符串ans就加一个方向,即‘D’,L,R,U中的任意一个&#…

 一看到题目用最短的路径,首先想到要用BFS,其次,要求记录路径,我们可以在状态里面添加字符串变量(也即我的代码里面的ans,每到达一个地点字符串ans就加一个方向,即‘D’,'L','R','U'中的任意一个),当到达右下角那个点时即可输出答案。

#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct node{
	int x, y;
	string ans;
	node(int _x, int _y, string _ans) {
		x = _x, y = _y;
		ans = _ans;
	}
};

bool mp[31][51];
bool d[31][51];
bool vis[31][51];

int dir[4][2] = {{1, 0}, {0, -1}, {0, 1}, {-1, 0}};
char td[4] = {'D', 'L', 'R', 'U'};
bool in (int x, int y) {
	return 0 <= x && x < 30 && 0 <= y && y < 50;
}
int main() {
	for (int i = 0; i < 30; i++) {
		scanf("%s", mp[i]);
	}
	queue<node> q;
	q.push(node(0, 0, ""));
	while (!q.empty()) {
		node first = q.front();
		q.pop();
		if (first.x == 29 && first.y == 49) {
			cout << first.ans << endl;
			break;
		}
		for (int i = 0; i < 4; i++) {
			int tx = first.x + dir[i][0];
			int ty = first.y + dir[i][1];
			if (in(tx, ty) && mp[tx][ty] != '1' && !vis[tx][ty]) {
				vis[tx][ty] = true;
				q.push(node(tx, ty, first.ans + td[i]));
				vis[tx][tx] = false;
			}
			
		}
	}
	return 0;
}

Input:

00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000

Output:

DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR

 


本文链接: http://www.dtmao.cc/news_show_300222.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?