逃离迷宫
给定一个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
#include<queue>
#include<cstdio>
#include<stdio.h>
#include<string.h>
using namespace std;
char maze[101][101];//地图面积
int vis[105][105]; //标记是否已经访问
int n,m; //分别代表行数和列数
int k,x1,y1,x2,y2;//最大转弯次数，起点，终点
int t;//代表有多少组
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; //所有方向
int flag; //标记是否完成
struct node{
int x,y,k;
};
void bfs(){
node now,next,bri;
//将起始坐标赋值给now
now.x = x1;
now.y = y1;
now.k = -1; //起初的方向不算，故从-1开始
vis[x1][y1]=1; //将起始坐标标记为已访问
queue<node> que;
que.push(now); //压入队列
while(que.size()){
now = que.front(); que.pop(); //将队列中的第一个给now，并弹出
if(now.x==x2&&now.y==y2&&now.k<=k){
//如果now为终点坐标并且转弯数小于最大转弯数 flag设为1
flag = 1;
}
for(int i = 0;i<4;i++){ //四个方向进行遍历
next.x = now.x+dir[i][0];
next.y = now.y+dir[i][1];
while(0<=next.x&&next.x<n&&0<=next.y&&next.y<m&&maze[next.x][next.y]=='.'){
/*
*思路： 一条路到底，一直走一个方向下去，并把该方向上可以访问的点压入队列
* 然后每个方向都是如此
* 例 (x1,y1)=(0,0) -->a (x2,y2)=(0,2) -->b
* step1 a_-1 ._0 ._0 *_ *_
* *_ ._ *_ *_ ._
* b_ ._ ._ ._ ._
* ._ ._ ._ ._ ._
* *_ ._ ._ ._ ._
*
* step2 a_-1 ._0 ._0 *_ *_
* *_ ._1 *_ *_ ._
* b_ ._1 ._ ._ ._
* ._ ._1 ._ ._ ._
* *_ ._1 ._ ._ ._
*
* step3 a_-1 ._0 ._0 *_ *_
* *_ ._1 *_ *_ ._3
* b_2 ._1 ._2 ._2 ._2
* ._2 ._1 ._2 ._2 ._2
* *_ ._1 ._2 ._2 ._2
*/
if(vis[next.x][next.y]==0){ //该点还未被访问
next.k = now.k+1;
vis[next.x][next.y] = 1; //标记该点为已访问
que.push(next);
}
bri.x = next.x + dir[i][0];
bri.y = next.y + dir[i][1];
next = bri;
}
}
}
//return;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i = 0;i<n;i++){
scanf("%s",&maze[i]);
}
memset(vis,0,sizeof(vis));
scanf("%d%d%d%d%d",&k,&y1,&x1,&y2,&x2);
x1-=1;y1-=1;x2-=1;y2-=1;
flag = 0;
bfs();
if(flag)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
如果用dfs，结果时间超时了，不过值得看看
/*
* 用dfs做 结果为时间超时了
*/
#include<stdio.h>
int m,n;//分别代表行数 列数
int t; //代表有几组测试数据
int direction; //代表当前方向
int dir[5][2]={{0,0},{0,1},{0,-1},{1,0},{-1,0}}; //所有方向
int count; //记录转弯次数
int maxcount; //最大能转弯的次数
int x1,y1,x2,y2; //代表起点终点的坐标
char maze[100][101]; //地图
int flag; //标记是否已经完成
void dfs(int x,int y){//x对应是列，y对应的是行
/*
*有几种情况
* 1.转弯次数已经超过了最大能转弯的次数,flag默认值为0
* 2. 已经找到可以到达的路径flag=1
*方向的记录
*解：将走的坐标以代号了记录
* (0,0) --> 0
* (0,1) --> 1
* (1,0) --> 2
* (0,-1)--> 3
* (-1,0)--> 4
*/
if(count>maxcount+1)//第一种情况
return;
if(flag)
return;
if(x==x2&&y==y2){//第二种情况
if(count<=maxcount+1)
flag=1;
return;
}
for(int i=1;i<5;i++){
int newx = x+dir[i][0];
int newy = y+dir[i][1];
int olddirection = direction;
if(0<=newx&&newx<n&&0<=newy&&newy<m&&maze[newy][newx]=='.'){
//首先该点必须在地图里面，并且是路即为'.'
/*
*思路： 从一个位置出发，往能走的地方一直走，直到走不了了，
然后退一步，转弯，继续上述过程
*/
if(direction!=i)
//如果direction与当前方向i不一样，代表转向了
count++;
direction=i; //再将新的方向给direction，无论方向变没变
dfs(newx,newy);
if(olddirection!=i)
count--;
direction=olddirection;
}
}
}
int main(){
scanf("%d",&t); //输入有多少组测试样例
while(t--){
//初始化
count=0;//因为第一次的方向不算转向，所有从-1开始
direction = 0; //让起始位置开始走的方向一定算进去了
flag =0; // flag开始就是未完成状态
scanf("%d%d",&m,&n);//m对应行数，n对应列数
for(int i = 0;i<m;i++){
scanf("%s",&maze[i]);
}
scanf("%d%d%d%d%d",&maxcount,&x1,&y1,&x2,&y2);
//x1,x2对应列，y1,y2对应行
//因为它坐标第一行是1，在电脑里是0
x1-=1;y1-=1;x2-=1;y2-=1;
dfs(x1,y1);
if(flag)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
京公网安备 11010502036488号