自己造的数据全都过了,但是交上去全wa了(真的找不到错QAQ)
#include<bits/stdc++.h>
using namespace std;
int n,m,vis[1005][1005],l,r;
int ma[1005][1005],sum[1005][1005],summ[1005][1005];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int dd[10]={1,2,4,8,16,32,64,128,256,512};
int main(){
cin>>n>>m;
getchar();
memset(vis,-1,sizeof(vis));
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
char c=getchar();
if(c=='#'){//记录终点
l=i;
r=j;
}
if(c=='X') ma[i][j]=1;//只要能走,就是0,不能走为1
}
getchar();
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
sum[i][j]=sum[i][j-1]+ma[i][j];
}
}//记录横着的前缀和
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
summ[i][j]=summ[i][j-1]+ma[j][i];
}
}//记录竖着的前缀和
vis[1][1]=0;
queue<int> que;
que.push(1);
que.push(1);
while(!que.empty()){//bfs搜索
int x=que.front();que.pop();
int y=que.front();que.pop();
int xx,yy;
for(int i=0;i<4;++i){
for(int j=0;j<10;++j){
xx=x+dx[i]*dd[j];
yy=y+dy[i]*dd[j];
if(xx>=1&&yy>=1&&xx<=n&&yy<=m&&vis[xx][yy]==-1&&ma[xx][yy]==0){
if(i==0){//下右上左 (前缀和不为零说明走不通)
if(summ[yy][xx]-summ[yy][x]!=0) break;
}
else if(i==1){
if(sum[xx][yy]-sum[xx][y]!=0) break;
}
else if(i==2){
if(summ[yy][x]-summ[yy][xx]!=0) break;
}
else{
if(sum[x][y]-sum[x][yy]!=0) break;
}
vis[xx][yy]=vis[x][y]+1;
que.push(xx);
que.push(yy);
}
}
}
}
cout<<vis[l][r];
return 0;
}