跳至正文

1 条题解

  • 0
    @ 2026-10-2 2:21:40

    使用广度优先搜索,标记起点,正确处理起终点相同及障碍。

    #include <bits/stdc++.h>
    using namespace std;
    int main(){int t;cin>>t;while(t--){int n;cin>>n;vector<string>a(n);for(auto&s:a)cin>>s;int x,y,u,v;cin>>x>>y>>u>>v;vector<vector<bool>>vis(n,vector<bool>(n));queue<pair<int,int>>q;if(a[x][y]!='#'){vis[x][y]=true;q.push({x,y});}while(!q.empty()){auto [r,c]=q.front();q.pop();for(auto [dr,dc]:vector<pair<int,int>>{{1,0},{-1,0},{0,1},{0,-1}}){int i=r+dr,j=c+dc;if(i>=0&&i<n&&j>=0&&j<n&&!vis[i][j]&&a[i][j]!='#'){vis[i][j]=true;q.push({i,j});}}}cout<<(vis[u][v]?"YES":"NO")<<"\n";}}
    
    • 1

    信息

    ID
    3891
    时间
    1000ms
    内存
    128MiB
    难度
    4
    标签
    递交数
    0
    已通过
    0
    上传者