原题链接

普通DFS——0分，Time Exceeded：

#include <queue>
#include <iostream>
using namespace std;
int n, m, sx, sy, ex, ey, ans = 0xfffffff, cnt, f[705][705];
int dx[] = {0, 1, -1, 0, 0};
int dy[] = {0, 0, 0, 1, -1};
char a[705][705], b[705][705];
bool vis[705][705];
bool check1(int x, int y)
{
    if (x < 1 || x > n)return 0;
    if (y < 1 || y > m)return 0;
    if (a[x][y] == '.')return 0;
    return 1;
}
bool check2(int x, int y)
{
    if (x < 1 || x > n)return 0;
    if (y < 1 || y > m)return 0;
    if (vis[x][y])return 0;
    return 1;
}
void dfs1(int x, int y)
{
    for (int i = 1; i <= 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (check1(nx, ny))
        {
            a[nx][ny] = '.';
            dfs1(nx, ny);
        }
    }
}
void dfs2(int x, int y)
{
    if (x == ex && y == ey)
    {
        ans = min(ans, cnt);
        return ;
    }
    for (int i = 1; i <= 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (check2(nx, ny))
        {
            if (b[nx][ny] == '.')cnt++;
            vis[nx][ny] = 1;
            dfs2(nx, ny);
            vis[nx][ny] = 0;
            if (b[nx][ny] == '.')cnt--;            
        }
    }
}
int main()
{
    for (int i = 0; i < 705; i++)
        for (int j = 0; j < 705; j++)
            f[i][j] = 0xfffffff;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            b[i][j] = a[i][j];
        }
    }
    bool flag = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] == 'X')
            {
                if (flag == 0)
                {
                    sx = i;
                    sy = j;
                    flag = 1;
                }
                else
                {
                    ex = i;
                    ey = j;
                }
                dfs1(i, j);
            }
        }
    }
    
    dfs2(sx, sy);
    cout << ans;
    return 0;
}

DFS+记忆化优化——70分，Time Exceeded：

#include <queue>
#include <iostream>
using namespace std;
//...
void dfs2(int x, int y)
{
    //...
    if (f[x][y] <= cnt)return ;
    f[x][y] = cnt;
    //...
}
int main()
{
    //...
    return 0;
}

普通BFS——6分，Memory Exceeded：

//...
void bfs()
{
    queue <stu> q;
    q.push(stu{sx, sy, 0});
    while (!q.empty())
    {
        stu f = q.front();
        q.pop();
        if (f.x == ex && f.y == ey)
        {
            cout << f.step;
            exit(0);
        }
        for (int i = 1; i <= 4; i++)
        {
            int nx = f.x + dx[i];
            int ny = f.y + dy[i];
            int nstep = f.step + 1;
            if (check2(nx, ny))
            {
                if (b[nx][ny] == '.')nstep--;
                q.push(stu{nx, ny, nstep});
            }
        }
    }
}
//...

BFS+奇怪的优化——40分， Wrong Answer：

//...
void bfs(int sx, int sy)
{
    //...
    while (!q.empty())
    {
        //...
        for (int i = 1; i <= 4; i++)
        {
            //...
            if (check2(nx, ny))
            {
                int nstep = f[t.x][t.y] + (b[nx][ny] == '.' ? 1 : 0);
                if (nstep < f[nx][ny])
                {
                    //...
                }
            }
        }
    }
}
//...

DeepSeekⅠ——82分,Runtime Error Segmentation fault：

#include <iostream>
#include <queue>
#include <climits>
using namespace std;

const int MX = 705;
int n, m, ans;
char g[MX][MX];
int d[MX][MX];
int qx[MX*MX], qy[MX*MX];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int s1x[MX*MX], s1y[MX*MX], s2x[MX*MX], s2y[MX*MX];
int c1, c2;

void bfs_mark(int sx, int sy, int id) 
{
    int h = 0, t = 0;
    qx[t] = sx;
    qy[t++] = sy;
    g[sx][sy] = 'V';
    
    while (h < t) 
    {
        int x = qx[h], y = qy[h++];
        
        if (id == 0) 
        {
            s1x[c1] = x;
            s1y[c1++] = y;
        } 
        else 
        {
            s2x[c2] = x;
            s2y[c2++] = y;
        }
        
        for (int i = 0; i < 4; i++) 
        {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] == 'X') 
            {
                g[nx][ny] = 'V';
                qx[t] = nx;
                qy[t++] = ny;
            }
        }
    }
}

int bfs_search() 
{
    int h = 0, t = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            d[i][j] = INT_MAX;
    
    for (int i = 0; i < c1; i++) 
    {
        d[s1x[i]][s1y[i]] = 0;
        qx[t] = s1x[i];
        qy[t++] = s1y[i];
    }
    
    while (h < t) 
    {
        int x = qx[h], y = qy[h++];
        
        for (int i = 0; i < 4; i++) 
        {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) 
            {
                int nd = d[x][y] + (g[nx][ny] == '.' ? 1 : 0);
                if (nd < d[nx][ny]) 
                {
                    d[nx][ny] = nd;
                    qx[t] = nx;
                    qy[t++] = ny;
                }
            }
        }
    }
    
    int res = INT_MAX;
    for (int i = 0; i < c2; i++)
        res = min(res, d[s2x[i]][s2y[i]]);
    return res;
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];
    
    int cnt = 0;
    for (int i = 1; i <= n && cnt < 2; i++)
        for (int j = 1; j <= m && cnt < 2; j++)
            if (g[i][j] == 'X') 
            {
                bfs_mark(i, j, cnt);
                cnt++;
            }
    
    ans = bfs_search();
    cout << ans << endl;
    
    return 0;
}

DeepSeekⅡ——100分，Accepted：

#include <iostream>
#include <queue>
#include <climits>
using namespace std;

const int MX = 710;  // 增加缓冲空间
int n, m, ans;
char g[MX][MX];
int d[MX][MX];
int qx[MX*MX], qy[MX*MX];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int s1x[MX*MX], s1y[MX*MX], s2x[MX*MX], s2y[MX*MX];
int c1 = 0, c2 = 0;  // 显式初始化

void bfs_mark(int sx, int sy, int id) 
{
    int h = 0, t = 0;
    qx[t] = sx;
    qy[t++] = sy;
    g[sx][sy] = 'V';
    
    while (h < t) 
    {
        int x = qx[h], y = qy[h++];
        
        if (id == 0) 
        {
            if(c1 >= MX*MX) return;  // 防止数组越界
            s1x[c1] = x;
            s1y[c1++] = y;
        } 
        else 
        {
            if(c2 >= MX*MX) return;  // 防止数组越界
            s2x[c2] = x;
            s2y[c2++] = y;
        }
        
        for (int i = 0; i < 4; i++) 
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] == 'X') 
            {
                g[nx][ny] = 'V';
                if(t >= MX*MX) return;  // 防止队列溢出
                qx[t] = nx;
                qy[t++] = ny;
            }
        }
    }
}

int bfs_search() 
{
    int h = 0, t = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            d[i][j] = INT_MAX;
    
    for (int i = 0; i < c1; i++) 
    {
        d[s1x[i]][s1y[i]] = 0;
        qx[t] = s1x[i];
        qy[t++] = s1y[i];
    }
    
    while (h < t) 
    {
        int x = qx[h], y = qy[h++];
        
        for (int i = 0; i < 4; i++) 
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) 
            {
                int nd = d[x][y] + (g[nx][ny] == '.' ? 1 : 0);
                if (nd < d[nx][ny]) 
                {
                    d[nx][ny] = nd;
                    if(t >= MX*MX) continue;  // 防止队列溢出
                    qx[t] = nx;
                    qy[t++] = ny;
                }
            }
        }
    }
    
    int res = INT_MAX;
    for (int i = 0; i < c2; i++)
        if(s2x[i] >= 1 && s2x[i] <= n && s2y[i] >= 1 && s2y[i] <= m)  // 边界检查
            res = min(res, d[s2x[i]][s2y[i]]);
    return res == INT_MAX ? 0 : res;  // 处理无解情况
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    if(n < 1 || n > 700 || m < 1 || m > 700) return 0;  // 输入验证
    
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];
    
    int cnt = 0;
    for (int i = 1; i <= n && cnt < 2; i++)
        for (int j = 1; j <= m && cnt < 2; j++)
            if (g[i][j] == 'X') 
            {
                bfs_mark(i, j, cnt);
                cnt++;
            }
    
    ans = bfs_search();
    cout << ans << endl;
    
    return 0;
}

D老师的题解