{
Direction d = GetInitialDirection(start);
int nSteps = 1;
Grid currentGrid = start, nextGrid;
while( currentGrid != exit)
{
GetLeftMost(currentGrid, d,nextGrid, d);
currentGrid = nextGrid;
nSteps ++;
}
return nSteps;
}
int findStepsForRightmost(const Grid &start, const Grid &exit)
{
Direction d = GetInitialDirection(start);
int nSteps = 1;
Grid currentGrid = start, nextGrid;
while( currentGrid != exit)
{
GetRightMost(currentGrid, d,nextGrid, d);
currentGrid = nextGrid;
nSteps ++;
}
return nSteps;
}
Grid q[2000];
bool GridLegal(const Grid &g)
{
if( g.r < 0 || g.r >= nRow || g.c < 0 || g.c >= nCol || g_Yard[g.r][g.c] == 1)
{
return false;
}
return true;
}
int BFS(const Grid &start, const Grid & exit)
{
int front, rear;
front = rear = 0;
q[rear++] = start;
while(rear > front)
{
Grid top = q[front];
if(top == exit)
{
return top.nSteps;
}
//iterate the neighboring
for(int i = 0; i < 4; i++)
{
Grid neighbor = GetNewPoint(top, i);
if(GridLegal(neighbor))// not visited
{
g_Yard[neighbor.r][neighbor.c] = 1;
q[rear++] = neighbor;
}
}
front++;
}
return -1;
}
int main()
{
int nCase;
scanf("%d", &nCase);
while(nCase--)
{
scanf("%d%d", &nCol, &nRow);
int i,j;
char c;
memset(g_Yard, 0, sizeof(g_Yard));
Grid start, exit;
for( i = 0; i < nRow; i++)
{
getchar();
for( j = 0; j < nCol; j++)
{
c = getchar();
if( c == '#')
{
g_Yard[i][j] = 1;
}
else if( c == 'S')
{
start.r = i;
start.c = j;
g_Yard[i][j] = 1;
}
else if( c == 'E')
{
exit.r = i;
exit.c = j;
}
}
}
int minSteps = 10000000;
int leftmost = findStepsForLeftmost(start, exit);
int rightmost = findStepsForRightmost(start, exit);
minSteps = BFS(start, exit);
printf("%d %d %d\n",leftmost ,rightmost, minSteps+1);
}
return 0;
}
作者：hopeztm