2014
01-05

# Escape

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).

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.

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.

2
9 13
#############
#@..........#
#####.#.#.#.#
#...........#
#.#.#.#.#.#.#
#.#.......#.#
#.#.#.#.#.#.#
#...........#
#####.#######
4 6
#.####
#.#.##
#...@#
######

31
-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;
}

1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

2. 可以参考算法导论中的时间戳。就是结束访问时间，最后结束的顶点肯定是入度为0的顶点，因为DFS要回溯

3. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮