魔法少女Clara有一个N*M的迷宫，他想让你告诉他，从起点出发到终点最少经过多少障碍物？

Input
第一行一个整数T(1 <= T <= 30), 表示数据组数，接下来T组数据：

每组数据第一行是两个整数N和M(2 <= N, M <= 300)，表示迷宫大小。

接下来N行，每行M个字母，表示Clara的迷宫。其中'#'表示障碍物, 'S'表示起点, 'T'表示终点, '.'表示空地。保证起点和终点都是空地。每次移动可以从当前所在空地移动到相邻的空地。保证每个迷宫中有且仅有一个S，有且仅有一个T。

Output
对于每组数据，在单独的一行中输出一个整数，表示Clara从起点出发到终点至少需要经过的障碍物数量。

Sample Input
2
5 5
S....
####.
.....
.####
....T
5 5
S....
####.
.###.
.####
....T


Sample Output
0
1

题目没有说“s必然在左上角，t必然在右下角”，这就导致代码复杂化。
怕就怕实际上所有测试都能保证“s必然在左上角，t必然在右下角”，然后就导致严格遵守题意的代码反而在效率上吃亏。

算法很简单: 当前位置的值 是四周4个位置的值中最小值再加0(如果当前位置是空地的话)，或加1(如果当前位置是障碍物的话)。
当整个矩阵的每一个位置都不再需要调整值时结束。

换成顺序步骤是，
将与s连通的所有空地标上0，与这些0相邻的障碍物标上1；
将与1连通的所有空地标上1(当然，已经标0的空地就不应该再标了)，与这些1相邻的障碍物标上2(当然，已经标1的障碍物就不应该再标了 );
……
一直到t出现为止。

我写了下迷宫代码,但是我不会标记障碍物连着障碍物,而且迷宫走的也有问题,请指教
#include<string.h>
#include<stdio.h>
int n,m;
typedef struct{
    int x; int y;
}pos;

int sx,sy,gx,gy;
const int base = -1;
char maze[105][105];
int d[105][105];
pos c[10005];
int dx[4] = {1,0,-1,0},dy[4]={0,1,0,-1};
int bfs(int n,int m){
   for( int i = 1 ; i <= n ; i++)
        {
            for( int j = 1 ; j <= m ; j++)
            {
                d[i][j] = base;
                scanf(" %c", &maze[i][j]);
                 if(maze[i][j] == 'S'){
                    sx = i;
                    sy = j;
                    }
                if(maze[i][j] == 'T'){
                    gx = i;
                    gy = j;
                    }
            }
        }
d[sx][sy] = 0;
int l = 0,r = 1;
while(l < r){
    sx = c[l].x;
    sy = c[l].y;
    l++;
       if(sx == gx && sy == gy)break;
       for(int i = 0 ; i < 4 ; i++){
           int nx = sx + dx[i],ny = sy + dy[i];
           if(0 <= nx && nx < m && 0 <= ny && ny < n && maze[nx][ny] != '#' && d[nx][ny] == base){
            maze[nx][ny] = 0;
               //d[nx][ny] = d[sx][sy] + 1;
               c[r].x = nx;
               c[r].y = ny;
               r++;
           }
           if(0 <= nx && nx < m && 0 <= ny && ny < n && maze[nx][ny] == '#'){
            maze[nx][ny] = 1;
            c[r].x = nx;
               c[r].y = ny;
               r++;
           }
       }
   }
   return d[gx][gy];
   }
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
    scanf("%d%d",&n,&m);
   int ans = bfs(n,m);
    printf("%d\n",ans);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) {
            printf("%d ", maze[i][j]);
        }
        printf("\n");
    }
    return 0;
}
}

步骤是这样的，只说思路。

1：首先先标记S的所有连通区域。S附近的障碍物也另外标记。
2：拆除所有标记S的障碍物，并且步数+1。
3：重复前两个步骤，直到找到出口T。

但问题是寻找拆除S附近的障碍物需要看算法复杂度。如果不考虑超时，可以最简单的就是全图搜索一次。如果超时则需要算法支持了。

根据 2楼 的数学定义写的代码，效率可能不高，但算法思路十分简洁

#include <stdio.h>
#include <stdbool.h>

unsigned foo( const char map[], unsigned row, unsigned col )
{
    unsigned buf[300*300];
    unsigned t_index;
    for( unsigned i=0; i!=row*col; ++i )
    {
        buf[i] = map[i]=='S' ? 0 : 999;
        if( map[i] == 'T' )
            t_index = i;
    }

    for( bool b=true; b; )
    {
        b = false;
        for( unsigned i=0; i!=row*col; ++i )
        {
            unsigned minval = buf[i] - (map[i]=='#');
            if( i>=col && buf[i-col]<minval )
                minval = buf[i-col];
            if( i<row*col-row && buf[i+col]<minval )
                minval = buf[i+col];
            if( i%col!=0 && buf[i-1]<minval )
                minval = buf[i-1];
            if( i%col!=col-1 && buf[i+1]<minval )
                minval = buf[i+1];
            minval += (map[i]=='#');

            if( buf[i] != minval )
            {
                buf[i] = minval;
                b = true;
            }
        }
    }
    return buf[t_index];
}

int main(void)
{
    unsigned t;
    scanf( "%u", &t );
    while( t-- )
    {
        unsigned n, m;
        char map[300*300];

        scanf( "%u%u", &n, &m );
        for( unsigned i=0; i!=n*m; ++i )
            scanf( " %c", &map[i] );

        printf( "%u\n", foo(map,n,m) );
    }
}

确实 tle 超时了

加个“脏”标志，可以快一倍（但也仅仅就是快了一倍而已）
你还是贴个原题链接吧！

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>

unsigned foo( const char map[], unsigned row, unsigned col )
{
    enum { ROW=300, COL=300, MAXSTEP=ROW*COL-3 };
    enum { DIRTY_BIT=1u<<(sizeof(unsigned)*CHAR_BIT-1), STEP_BITS=~DIRTY_BIT };

    unsigned buf[ROW*COL];
    unsigned s_index, t_index;
    for( unsigned i=0; i!=row*col; ++i )
    {
        buf[i] = MAXSTEP;
        if( map[i] == 'S' )
            s_index = i;
        else if( map[i] == 'T' )
            t_index = i;
    }
    buf[s_index] = 0;
    if( s_index>=col )
        buf[s_index-col] |= DIRTY_BIT;
    if( s_index<row*col-row )
        buf[s_index+col] |= DIRTY_BIT;
    if( s_index%col!=0 )
        buf[s_index-1] |= DIRTY_BIT;
    if( s_index%col!=col-1 )
        buf[s_index+1] |= DIRTY_BIT;

    for( bool b=true; b; )
    {
        b = false;
        for( unsigned i=0; i!=row*col; ++i )
        {
            if( (buf[i]&DIRTY_BIT) == 0 )
                continue;

            unsigned minval = (buf[i]&STEP_BITS) - (map[i]=='#');
            if( i>=col && (buf[i-col]&STEP_BITS)<minval )
                minval = buf[i-col]&STEP_BITS;
            if( i<row*col-row && (buf[i+col]&STEP_BITS)<minval )
                minval = buf[i+col]&STEP_BITS;
            if( i%col!=0 && (buf[i-1]&STEP_BITS)<minval )
                minval = buf[i-1]&STEP_BITS;
            if( i%col!=col-1 && (buf[i+1]&STEP_BITS)<minval )
                minval = buf[i+1]&STEP_BITS;
            minval += (map[i]=='#');

            if( (buf[i]&STEP_BITS) != minval )
            {
                b = true;
                if( i>=col )
                    buf[i-col] |= DIRTY_BIT;
                if( i<row*col-row )
                    buf[i+col] |= DIRTY_BIT;
                if( i%col!=0 )
                    buf[i-1] |= DIRTY_BIT;
                if( i%col!=col-1 )
                    buf[i+1] |= DIRTY_BIT;
            }
            buf[i] = minval;
        }
    }
    return buf[t_index];
}

int main( void )
{
    unsigned t;
    scanf( "%u", &t );
    while( t-- )
    {
        unsigned n, m;
        char map[300*300];

        scanf( "%u%u", &n, &m );
        for( unsigned i=0; i!=n*m; ++i )
            scanf( " %c", &map[i] );

        printf( "%u\n", foo(map,n,m) );
    }
}