本题知识点：深度优先搜索 + 宽度优先搜索
本题题意是求三个路径长度，第一个是一直往左手边走的距离，第二个是一直往右手边走的距离，第三个是最短距离。
第三个很好办，就是一个简单的bfs的模板，问题出在第一二个。
但第一二个只是方向的丝丝不同，所以会其中一个也就解决了。
读懂题意后很简单，问题是怎么简单高效地实现。
推荐这篇博客
一些感慨：该题做了我差不多4个小时吧，前前后后de了bug又发现有新bug，包括调试的代码，旧代码起码达到了300多行。已经有东西南北方向的想法了，可就是差那么一点点。还是刷题不够吧。总之这4个小时里感到兴奋的心情比难过迷茫的心情要多很多。还是要以学习算法为前提去A题才是快乐A题呀！
// 3083
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;char maze[50][50];
bool take[50][50];
int len[50][50];
int T, W, H, now;
int bh, bw, eh, ew;
int left_len, right_len, min_len;
bool ok;
struct node{
int h, w;
};
queue<node> que;
int rw[] = { -1, 0, 1, 0 };
int rh[] = { 0, 1, 0, -1 };bool check(int h, int w){
if(0 <= h && h < H && 0 <= w && w < W && maze[h][w] != '#' && !take[h][w]) return true;
return false;
}void build(int W, int H){
memset(take, false, sizeof(take));
left_len = right_len = min_len = 0;
for(int i = 0; i < H; i++){
scanf("%s", maze[i]);
for(int j = 0; j < W; j++){
if(maze[i][j] == 'S'){
bh = i; bw = j;
// maze[i][j] = '#';
}
if(maze[i][j] == 'E'){
eh = i; ew = j;
}
}
}
if(bh == 0) now = 2;
else if(bh == H - 1) now = 0;
else if(bw == 0) now = 3;
else if(bw == W - 1) now = 1;
}void l_dfs(int h, int w, int go){
left_len++;
// take[h][w] = true;
if(h == eh && w == ew){
ok = true;
return ;
} switch(go)
{
case 0:
{
if(check(h, w - 1)) l_dfs(h, w - 1, 1);
else if(check(h - 1, w)) l_dfs(h - 1, w, 0);
else if(check(h, w + 1)) l_dfs(h, w + 1, 3);
else if(check(h + 1, w)) l_dfs(h + 1, w, 2);
break;
}
case 1:
{
if(check(h + 1, w)) l_dfs(h + 1, w, 2);
else if(check(h, w - 1)) l_dfs(h, w - 1, 1);
else if(check(h - 1, w)) l_dfs(h - 1, w, 0);
else if(check(h, w + 1)) l_dfs(h, w + 1, 3);
break;
}
case 2:
{
if(check(h, w + 1)) l_dfs(h, w + 1, 3);
else if(check(h + 1, w)) l_dfs(h + 1, w, 2);
else if(check(h, w - 1)) l_dfs(h, w - 1, 1);
else if(check(h - 1, w)) l_dfs(h - 1, w, 0);
break;
}
case 3:
{
if(check(h - 1, w)) l_dfs(h - 1, w, 0);
else if(check(h, w + 1)) l_dfs(h, w + 1, 3);
else if(check(h + 1, w)) l_dfs(h + 1, w, 2);
else if(check(h, w - 1)) l_dfs(h, w - 1, 1);
break;
}
}}void r_dfs(int h, int w, int go){
right_len++;
if(h == eh && w == ew){
ok = true;
return ;
} switch(go)
{
case 0:
{
if(check(h, w + 1)) r_dfs(h, w + 1, 3);
else if(check(h - 1, w)) r_dfs(h - 1, w, 0);
else if(check(h, w - 1)) r_dfs(h, w - 1, 1);
else if(check(h + 1, w)) r_dfs(h + 1, w, 2);
break;
}
case 1:
{
if(check(h - 1, w)) r_dfs(h - 1, w, 0);
else if(check(h, w - 1)) r_dfs(h, w - 1, 1);
else if(check(h + 1, w)) r_dfs(h + 1, w, 2);
else if(check(h, w + 1)) r_dfs(h, w + 1, 3);
break;
}
case 2:
{
if(check(h, w - 1)) r_dfs(h, w - 1, 1);
else if(check(h + 1, w)) r_dfs(h + 1, w, 2);
else if(check(h, w + 1)) r_dfs(h, w + 1, 3);
else if(check(h - 1, w)) r_dfs(h - 1, w, 0);
break;
}
case 3:
{
if(check(h + 1, w)) r_dfs(h + 1, w, 2);
else if(check(h, w + 1)) r_dfs(h, w + 1, 3);
else if(check(h - 1, w)) r_dfs(h - 1, w, 0);
else if(check(h, w - 1)) r_dfs(h, w - 1, 1);
break;
}
}
}void bfs(){
len[bh][bw] = 1;
while(!que.empty()){
node now = que.front(), next; que.pop();
int d = len[now.h][now.w];
// printf("d:%d\n", d);
if(now.h == eh && now.w == ew) break;
for(int i = 0; i < 4; i++){
next.h = now.h + rh[i]; next.w = now.w + rw[i];
if(check(next.h, next.w)) {
take[next.h][next.w] = true;
len[next.h][next.w] = d + 1;
que.push(next);
}
}
}
}int main()
{
scanf("%d", &T);
while(T--){
scanf("%d %d", &W, &H);
build(W, H); // right
ok = false;
memset(take, false, sizeof(take));
l_dfs(bh, bw, now);
// cout << endl; ok = false;
memset(take, false, sizeof(take));
r_dfs(bh, bw, now); while(!que.empty()) que.pop();
memset(take, false, sizeof(take));
memset(len, 0, sizeof(len));
node a; a.h = bh; a.w = bw;
que.push(a);
bfs(); printf("%d %d %d\n", left_len, right_len, len[eh][ew]);
} return 0;
}//6
//8 8
//########
//#......#
//#.####.#
//#.####.#
//#.####.#
//#.####.#
//#...#..#
//#S#E####
//9 5
//#########
//#.#.#.#.#
//S.......E
//#.#.#.#.#
//#########
//8 8
//########
//#......#
//#.####.#
//#.####.#
//#.####.#
//#.####.#
//#..#...#
//####E#S#
//9 5
//#########
//#.#.#.#.#
//E.......S
//#.#.#.#.#
//#########
//9 9
//####E####
//#.......#
//#..#.#..#
//#..###..#
//#.......#
//#..#.#..#
//#..#.#..#
//#..#.#..#
//####S####
//9 9
//####S####
//#.......#
//#..#.#..#
//#.#####.#
//#.......#
//#..#.#..#
//#..#.#..#
//#..#.#..#
//####E####
