hdu2364之BFS
2024-10-20 17:29:51
Escape
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 569 Accepted Submission(s): 227
Problem Description
You find yourself trapped in a large rectangular room, made up of large square tiles; some are accessible, others are blocked by obstacles or walls. With a single step, you can move from one tile to another tile if it is horizontally or vertically adjacent (i.e. you cannot move diagonally).
To shake off any people following you, you do not want to move in a straight line. In fact, you want to take a turn at every opportunity, never moving in any single direction longer than strictly necessary. This means that if, for example, you enter a tile from the south, you will turn either left or right, leaving to the west or the east. Only if both directions are blocked, will you move on straight ahead. You never turn around and go back!
Given a map of the room and your starting location, figure out how long it will take you to escape (that is: reach the edge of the room).
To shake off any people following you, you do not want to move in a straight line. In fact, you want to take a turn at every opportunity, never moving in any single direction longer than strictly necessary. This means that if, for example, you enter a tile from the south, you will turn either left or right, leaving to the west or the east. Only if both directions are blocked, will you move on straight ahead. You never turn around and go back!
Given a map of the room and your starting location, figure out how long it will take you to escape (that is: reach the edge of the room).
Input
On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:
a line with two integers separated by a space, h and w (1 <= h, w <= 80), the height and width of the room;
then h lines, each containing w characters, describing the room. Each character is one of . (period; an accessible space), # (a blocked space) or @ (your starting location).
There will be exactly one @ character in each room description.
Output
For each test case:
A line with an integer: the minimal number of steps necessary to reach the edge of the room, or -1 if no escape is possible.
Sample Input
2
9 13
#############
#@..........#
#####.#.#.#.#
#...........#
#.#.#.#.#.#.#
#.#.......#.#
#.#.#.#.#.#.#
#...........#
#####.#######
4 6
#.####
#.#.##
#...@#
######
9 13
#############
#@..........#
#####.#.#.#.#
#...........#
#.#.#.#.#.#.#
#.#.......#.#
#.#.#.#.#.#.#
#...........#
#####.#######
4 6
#.####
#.#.##
#...@#
######
Sample Output
31
-1
-1
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std; const int MAX=80+10;
char Map[MAX][MAX];
int mark[MAX][MAX][5];//到达i,j是以方向k到达的是否标记
int t,n,m;
int dir[4][2]={0,1,1,0,0,-1,-1,0}; struct Node{
int x,y,time,dir;
Node(){}
Node(int X,int Y,int Time,int Dir):x(X),y(Y),time(Time),dir(Dir){}
}start; int BFS(int flag){
if(start.x == 0 || start.y == 0 ||start.x == n-1 || start.y == m-1)return 0;
queue<Node>q;
Node oq,next;
q.push(start);
mark[start.x][start.y][0]=mark[start.x][start.y][1]=flag;
mark[start.x][start.y][2]=mark[start.x][start.y][3]=flag;
while(!q.empty()){
oq=q.front();
q.pop();
bool f=true;//标记是否只能直走
for(int i=0;i<4;++i){
if(i%2 == oq.dir%2)continue;
next=Node(oq.x+dir[i][0],oq.y+dir[i][1],oq.time+1,i);
if(next.x<0 || next.y<0 || next.x>=n || next.y>=m)continue;
if(Map[next.x][next.y] == '#')continue;
f=false;//左右可以走(无论以前是否走过)
if(mark[next.x][next.y][i] == flag)continue;
mark[next.x][next.y][i]=flag;
if(next.x == 0 || next.y == 0 || next.x == n-1 || next.y == m-1)return next.time;
q.push(next);
}
if(f){//只能直走
int i=oq.dir;
next=Node(oq.x+dir[i][0],oq.y+dir[i][1],oq.time+1,i);
if(next.x<0 || next.y<0 || next.x>=n || next.y>=m)continue;
if(Map[next.x][next.y] == '#' || mark[next.x][next.y][i] == flag)continue;
mark[next.x][next.y][i]=flag;
if(next.x == 0 || next.y == 0 || next.x == n-1 || next.y == m-1)return next.time;
q.push(next);
}
}
return -1;
} int main(){
cin>>t;
while(t--){
cin>>n>>m;
for(int i=0;i<n;++i)cin>>Map[i];
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
if(Map[i][j] == '@')start.x=i,start.y=j;
}
}
start.time=0,start.dir=-1;
cout<<BFS(t+1)<<endl;
}
return 0;
}
最新文章
- DBC表名说明
- 用andtoid studio获取天气数据并解析适配
- 线段树(segment tree)
- Unity 3D Intantiate过程中Transform 空物体和本体之间的关系
- ThinkPHP的增、删、改、查
- uva 242
- VB断点大全
- __init和__exit宏的作用
- C 头文件阅读理解
- IOS7官方推荐图标和图像尺寸
- java http 分段下载
- 在Python中使用正则表达式同时匹配邮箱和电话并进行简单的分类
- Android 定义自己的学习(5)它们的定义Progressbar
- Visual Studio Code 使用Chrome Debug 代码
- Automated Front End Test - Xvfb, Chromedriver, Selenium, Jenkins
- 【Kafka】操作命令
- python 下载新的模块
- Scala的类层级讲解
- VLAN原理解释
- pip命令出现了问题,提示说找不到ssl模块