新人不懂为什么超时和RE
查看原帖
新人不懂为什么超时和RE
666682
songsonghui楼主2022/2/27 18:06
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;

int n,step[1005][1005],x1,x2,y1,y2;
char map[1005][1005];
int dx[] = {0,-1,0,1};
int dy[] = {-1,0,1,0};
typedef pair<int,int> s;
queue<s> q;
bool check(int x,int y){
	if(x<1 ||x>n||y<1||y>n) return false;
	if(map[x][y] =='1') return false;
//	else printf("\n(%d,%d):%c:%s\n",x,y,map[x][y],map[x]+1);
	return true; 
}
int main(int argc, char** argv) {
	memset(map,'1',sizeof(map));
	memset(step,0,sizeof(step));
	scanf("%d",&n);
	for(int i =1;i<=n;i++){
			scanf("%s",map[i]+1);
	}
	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
	s a(y1,x1);
	q.push(a);
	
	while(!q.empty()){
		s top = q.front();
		q.pop();
		for(int i = 0;i<4;i++){
			if(check(top.first+dy[i],top.second+dx[i])){
				s b(top.first+dy[i],top.second+dx[i]);
				q.push(b);
				step[top.first+dy[i]][top.second+dx[i]] = step[top.first][top.second] +1;
				map[top.first][top.second] = '1';
			}
		}
//		for(int i = 1;i<=n;i++){
//			for(int j = 1;j<=n;j++){
//				printf("%d",step[i][j]);	
//			} 
//		printf("\n");
//		}
//		printf("\n");
		if(step[y2][x2] !=0) break; 
	}
	printf("%d",step[y2][x2]);
	return 0;
}
2022/2/27 18:06
加载中...