全wa了,蒟蒻求助
查看原帖
全wa了,蒟蒻求助
292029
幽理家的男人楼主2020/9/26 10:28

自己造的数据全都过了,但是交上去全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;
}
2020/9/26 10:28
加载中...