#include <stdio.h>
#include <string.h>
#define N 50
struct point
{
int x, y;
int dir; //方向:上右下左分别是0 1 2 3
int step; //dfs的时候用此来计数找了几个方向了
}start, end;
struct point dir[2][4] = {{{-1, 0, 0, 0}, {0, -1, 0, 0}, {1, 0, 0, 0}, {0, 1, 0, 0}},
{{1, 0, 0, 0}, {0, -1, 0, 0}, {-1, 0, 0, 0}, {0, 1, 0, 0}}};
char g[N][N];
int step;
int cur_dir;
struct point queue[N*N], stack[N*N], tmp_pos, cur_pos;
int mark[N][N];
int place(int w, int h, struct point p)
{
if(p.x < 0 || p.x >= w || p.y < 0 || p.y >= h || g[p.y][p.x] == '#')
return 0;
return 1;
}
int dfs(int h, int w, int how)
{
int top = 0, i;
start.dir = -1;
start.step = 1;
stack[top++] = start;
while (top > 0)
{
cur_pos = stack[top-1];
for (i=(cur_pos.dir+1)%4, cur_pos.step; cur_pos.step<=4; i=(i+1)%4, cur_pos.step++)
{
tmp_pos.x = cur_pos.x + dir[how][i].x;
tmp_pos.y = cur_pos.y + dir[how][i].y;
if(place(w, h, tmp_pos))
{
break;
}
}
stack[top-1].step = cur_pos.step;
if(cur_pos.step<=4)
{
step++;
if(tmp_pos.x == end.x && tmp_pos.y == end.y)
return step;
stack[top-1].dir = i;
tmp_pos.dir = (i+6) % 4;
tmp_pos.step = 1;
stack[top++] = tmp_pos;
}
else
{
step++;
top--;
}
}
return step;
}
int bfs(int w, int h)
{
int rear, head;
int i;
mark[start.y][start.x] = 1;
head = rear = 0;
queue[head++] = start;
while(head > rear)
{
cur_pos = queue[rear++];
for(i=0; i<4; i++)
{
tmp_pos.x = cur_pos.x + dir[0][i].x;
tmp_pos.y = cur_pos.y + dir[0][i].y;
if(place(w, h, tmp_pos) && mark[tmp_pos.y][tmp_pos.x] == 0)
{
tmp_pos.step = cur_pos.step + 1;
if(tmp_pos.x == end.x && tmp_pos.y == end.y)
return tmp_pos.step;
queue[head++] = tmp_pos;
mark[tmp_pos.y][tmp_pos.x] = 1;
}
}
}
return step;
}
int main()
{
int w, h, n, i, j, k; scanf("%d", &n);
for(k=0; k<n; k++)
{
scanf("%d %d", &w, &h);
for(i=0; i<h; i++)
for(j=0; j<w; j++)
{
scanf(" %c", &g[i][j]);
if(g[i][j] == 'S')
{ start.x = j; start.y = i; }
if(g[i][j] == 'E')
{ end.x = j; end.y = i; }
}
//左优先
step = 1;
dfs(h, w, 0);
printf("%d", step);
//右优先
step = 1;
dfs(h, w, 1);
printf(" %d", step);
//最短
memset(mark, 0, sizeof(mark));
printf(" %d\n", bfs(w, h));
}
return 0;
}
|