995 WA90分

xmy201315 @ 2024-12-08 20:39:38

#include <bits/stdc++.h>
using namespace std;
int n,m;
char s[1005][1005];
const int D[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int q[100005][2],dist[1005][1005];
bool bfs(int sx,int sy,int ex,int ey){
    memset(dist,255,sizeof(dist));
    int f=1,r=1;
    q[1][0]=sx,q[1][1]=sy;
    dist[sx][sy]=0;
    while(f<=r){
        int x=q[f][0],y=q[f][1];
        ++f;
        for(int i=0;i<4;i++){
            int xx=x+D[i][0],yy=y+D[i][1];
            if(xx<0||xx>n||yy<0||yy>m)continue;
            if(s[xx][yy]!='#'&&dist[xx][yy]==-1)dist[xx][yy]=dist[x][y]+1,
            q[++r][0]=xx,q[r][1]=yy;
        }
    }
    if(dist[ex][ey]!=-1)return true;
    return false;
}
int main(){     
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)cin>>s[i]+1;
    if(bfs(1,1,n,m))puts("Yes");
    else puts("No");
}

5 5
.....
##.##
#####
.....
.....

by xmy201315 @ 2024-12-08 20:41:37

本地测为

Yes

实际为

No

by wawatime1 @ 2024-12-08 21:03:32

你是哪个代码源的吗？

by xiezt123456 @ 2024-12-08 21:03:33

@xmy201315

可能的问题点：

边界条件：\ 在 BFS 中，你检查了 xx < 0~||~ xx > n ~||~ yy < 0~ || ~yy > m ，但是这些条件应该是 xx < 1~ || ~xx > n ~|| ~yy < 1 ~|| ~yy > m~ ，因为矩阵是从 1 开始索引的。

起始点和终点是否可达：\ 确保起点和终点不是障碍物。

修改建议：

修正边界条件检查。\ 确保起点和终点是可达的。

AC CODE

#include <bits/stdc++.h>
using namespace std;
int n, m;
char s[1005][1005];
const int D[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int q[100005][2], dist[1005][1005];
bool bfs(int sx, int sy, int ex, int ey) {
    memset(dist, -1, sizeof(dist)); 
    int f = 1, r = 1;
    q[1][0] = sx, q[1][1] = sy;
    dist[sx][sy] = 0;
    while (f <= r) {
        int x = q[f][0], y = q[f][1];
        ++f;
        for (int i = 0; i < 4; i++) {
            int xx = x + D[i][0], yy = y + D[i][1];
            if (xx < 1 || xx > n || yy < 1 || yy > m) continue; 
            if (s[xx][yy] != '#' && dist[xx][yy] == -1) {
                dist[xx][yy] = dist[x][y] + 1;
                q[++r][0] = xx; q[r][1] = yy;
            }
        }
    }
    return dist[ex][ey] != -1; 
}
int main() {        
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) cin >> s[i] + 1;
    if (bfs(1, 1, n, m)) puts("Yes");
    else puts("No");
}

by wawatime1 @ 2024-12-08 21:05:57

你的广搜好奇怪呀

by xiezt123456 @ 2024-12-08 21:08:18

@xmy201315有个人名字@xmy2013

by xmy201315 @ 2024-12-08 21:25:34

@wawatime1,本人代码源账号xmy2013,atcoder xmy1234567890,codeforces xmy1234567890

by xmy201315 @ 2024-12-08 21:28:23

@xiezt123456,谢谢指出错误，洛谷上有一个账号名叫xmy2013，他不是我的小号，请众知悉