Day2-J-逃离迷宫-HDU-1728
2024-10-08 14:57:45
给定一个m × n (m行, n列)的迷宫,迷宫中有两个位置,gloria想从迷宫的一个位置走到另外一个位置,当然迷宫中有些地方是空地,gloria可以穿越,有些地方是障碍,她必须绕行,从迷宫的一个位置,只能走到与它相邻的4个位置中,当然在行走过程中,gloria不能走到迷宫外面去。令人头痛的是,gloria是个没什么方向感的人,因此,她在行走过程中,不能转太多弯了,否则她会晕倒的。我们假定给定的两个位置都是空地,初始时,gloria所面向的方向未定,她可以选择4个方向的任何一个出发,而不算成一次转弯。gloria能从一个位置走到另外一个位置吗?
Input 第1行为一个整数t (1 ≤ t ≤ 100),表示测试数据的个数,接下来为t组测试数据,每组测试数据中,
第1行为两个整数m, n (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数,接下来m行,每行包括n个字符,其中字符'.'表示该位置为空地,字符'*'表示该位置为障碍,输入数据中只有这两种字符,每组测试数据的最后一行为5个整数k, x 1, y 1, x 2, y 2 (1 ≤ k ≤ 10, 1 ≤ x1, x 2 ≤ n, 1 ≤ y 1, y 2 ≤ m),其中k表示gloria最多能转的弯数,(x 1, y 1), (x 2, y2)表示两个位置,其中x 1,x 2对应列,y 1, y 2对应行。
Output 每组测试数据对应为一行,若gloria能从一个位置走到另外一个位置,输出“yes”,否则输出“no”。Sample Input
2
5 5
...**
*.**.
.....
.....
*....
1 1 1 1 3
5 5
...**
*.**.
.....
.....
*....
2 1 1 1 3
Sample Output
no
yes 分析:简单的BFS搜索最短路径,加上一个转弯的限制,就在判重的时候多加一个条件即可,但是直接判断是否访问过会造成漏解,剪枝条件应为:在该点的朝向的剩余转向次数
是否大于等于该点已经访问(未访问)过的(等于是为了防止0转向次数被剪掉),相当于转弯次数为优先级,越多其对解的贡献越大。
代码如下:
const int maxm = ;
const int dx[] = {-, , , };
const int dy[] = {, , -, }; struct Node {
int x, y, turn, dire;
Node(int _x = , int _y = , int _turn = -,int _dire = -):x(_x), y(_y),turn(_turn),dire(_dire) {}
}; int T, m, n, sx, sy, ex, ey, k, d[maxm][maxm][];
string buf[maxm]; bool inside(int x,int y) {
return x >= && x < m && y >= && y < n;
} bool bfs() {
memset(d, -, sizeof(d));
queue<Node> q;
for (int i = ; i < ; ++i) {
q.push(Node(sx, sy, k, i));
d[sx][sy][i] = k;
}
while (!q.empty()){
Node p = q.front();
q.pop();
if(p.x == ex && p.y == ey)
return true;
for (int i = ; i < ; ++i) {
Node tmp = p;
tmp.x += dx[i], tmp.y += dy[i];
if(i == p.dire) {
if(inside(tmp.x, tmp.y) && buf[tmp.x][tmp.y] == '.' && d[tmp.x][tmp.y][i] <= p.turn) {
d[tmp.x][tmp.y][i] = p.turn;
q.push(tmp);
}
} else if (tmp.turn > ) {
tmp.turn--, tmp.dire = i;
if(inside(tmp.x, tmp.y) && buf[tmp.x][tmp.y] == '.' && d[tmp.x][tmp.y][i] <= p.turn) {
d[tmp.x][tmp.y][i] = p.turn;
q.push(tmp);
}
}
}
}
return false;
} int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d", &m, &n);
for (int i = ; i < m; ++i)
cin >> buf[i];
scanf("%d%d%d%d%d", &k, &sy, &sx, &ey, &ex);
sy--, sx--, ey--, ex--;
if(bfs())
printf("yes\n");
else
printf("no\n");
}
return ;
}
虽然我们用转向次数大于等于的判断条件来使0转向次数不被剪掉,但也加入了许多重复的点,我们可以继续优化代码,既然转向后次数减少,那么对解的贡献也减小,到达相同的点相同的方向的优先级一定小于不转弯的,那么,我们可以做出如下策略:如果不转弯,直接将前进后的入队,如果转弯,只转弯不前进入队,这样,转弯的情况就比直走慢了一步,自然就会有优先级上的差别,直接上代码进行体会:
const int maxm = ;
const int dx[] = {-, , , };
const int dy[] = {, , -, }; struct Node {
int x, y, turn, dire;
Node(int _x = , int _y = , int _turn = -,int _dire = -):x(_x), y(_y),turn(_turn),dire(_dire) {}
}; int T, m, n, sx, sy, ex, ey, k, d[maxm][maxm][];
string buf[maxm]; bool inside(int x,int y) {
return x >= && x < m && y >= && y < n;
} bool bfs() {
memset(d, , sizeof(d));
queue<Node> q;
for (int i = ; i < ; ++i) {
q.push(Node(sx, sy, k, i));
d[sx][sy][i] = k;
}
while (!q.empty()){
Node p = q.front();
q.pop();
if(p.x == ex && p.y == ey)
return true;
for (int i = ; i < ; ++i) {
Node tmp = p;
if(i == p.dire) {
tmp.x += dx[i], tmp.y += dy[i];
if(inside(tmp.x, tmp.y) && buf[tmp.x][tmp.y] == '.' && !d[tmp.x][tmp.y][i]) {
d[tmp.x][tmp.y][i] = ;
q.push(tmp);
}
} else if (tmp.turn > ) {
tmp.turn--, tmp.dire = i;
if(!d[tmp.x][tmp.y][i]) {
d[tmp.x][tmp.y][i] = ;
q.push(tmp);
}
}
}
}
return false;
} int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d", &m, &n);
for (int i = ; i < m; ++i)
cin >> buf[i];
scanf("%d%d%d%d%d", &k, &sy, &sx, &ey, &ex);
sy--, sx--, ey--, ex--;
if(bfs())
printf("yes\n");
else
printf("no\n");
}
return ;
}
从110ms降到了60ms,代码上只进行了基础微调。
最新文章
- javascript数据结构-链表
- c#模拟表单POST数据,并获取跳转之后的页面
- 通过google chrome操作JavaScript中Console
- excel曲线拟合怎么弄
- 解决android 启动白屏问题
- linux卸载php
- 搭建和使用Docker私有仓库
- [Guava源码分析]Objects 和 ComparisonChain:帮助重写Object方法
- C#微信开发之旅--基本信息的回复
- 动态规划——数位dp
- [oracle]删除一张表中重复数据,保留其id字段最小的sql
- RadioGroup单选按钮排版
- linux学习小记:如何查看linux服务器的cpu数量,内核数,和cpu线程数
- nagios安装及监控Linux主机
- UI --UIView 及其子类
- python_flask 基础巩固(自定义URL转换器)
- nginx强制使用https访问(http跳转到https)
- 把一张图片变成base64
- Visualforce简介
- Android Studio安卓导出aar包与Unity 3D交互