U592279 2.吉祥照相馆（photo）：题解

admin_wyh · 2025-08-17 13:36:24 · 题解

题目大意

本题是一个典型的迷宫寻路问题，需要判断阿昌从起点 (0,0) 能否在规定时间 t 内到达终点 (n,m) 。迷宫中包含三种元素：

• J：日本人（障碍，无法通过）
• #：墙（障碍，无法通过）
• .：路（可以通行）

我们需要找到从起点到终点的最短路径，并判断其是否在规定时间 t 以内。

思路

广搜(BFS) 模版题。

• 使用队列存储待访问的位置及到达该位置的时间。
• 从起点开始，向四个方向（上下左右）探索可通行的位置。
• 一旦到达终点，立即返回所用时间。
• 比较最短时间与规定时间 t，输出结果。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long 
// 方向数组，代表上下左右四个方向
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char ma[2024][2024];  // 存储迷宫
bool vis[2024][2024]={0};  // 标记是否访问过
int n,m,t;

// 队列中的节点结构，存储当前位置和到达时间
struct node
{
    int h,l,sum;
}f;

queue<node>q;

int bfs()
{
    q.push({1,1,0});  // 起点入队（注意这里使用1-based索引）
    while(!q.empty())
    {
        f=q.front();
        q.pop();
        // 到达终点，返回
        if(f.h==n&&f.l==m) return 0;
        // 探索四个方向
        for(int i=0;i<=3;i++)
        {
            int hh=dir[i][0]+f.h;
            int ll=dir[i][1]+f.l;
            // 检查是否在迷宫范围内，是否可通行，是否未访问过
            if(hh>=1&&hh<=n&&ll>=1&&ll<=m&&ma[hh][ll]=='.'&&vis[hh][ll]==0) 
            {
                q.push({hh,ll,f.sum+1});  // 入队，时间+1
                vis[hh][ll]=1;  // 标记为已访问
            }
        }
    }
    return 1;  // 无法到达终点
}

signed main()
{
    cin>>n>>m;
    cin>>t;
    // 读取迷宫
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>ma[i][j];
    // 执行BFS并判断结果
    if(bfs()==0&&f.sum<=t) cout<<"YES"<<endl<<f.sum;
    else cout<<"NO"<<endl;
    return 0;    
}