70分!!!本蒟蒻求助
查看原帖
70分!!!本蒟蒻求助
531319
thomaswmy楼主2021/9/7 19:59
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int dx[]={0,0,1,-1,1,1,-1,-1};
const int dy[]={1,-1,0,0,1,-1,1,-1};

struct point{
	int x,y,step;
};

point q[1000000],s,e;
int n,m;
char c,tmp[10];
int front,tail;
int x,y;
bool flag,end[3000][3000],maze[3000][3000],used[3000][3000];

int main() {
	scanf("%d%d",&n,&m);
	gets(tmp);
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			scanf("%c",&c);
			if(c=='O') maze[i][j]=1;
			else maze[i][j]=0;
		}
		gets(tmp);
	}
	
	
	
	while(true) {
		scanf("%d%d%d%d",&e.x,&e.y,&s.x,&s.y);
		if(s.x==0 && s.y==0 && e.x==0 && e.y==0) break;
		if(s.x==e.x && s.y==e.y) {
			printf("0\n");
			continue;
		}
		memset(used,0,sizeof(used));
		memset(end,0,sizeof(end));
		s.step=0;
		for(int i=0;i<8;i++) {
			x=e.x,y=e.y;
			while(maze[x][y]==1 && x>=1 && x<=n && y>=1 && y<=m) {
				end[x][y]=1;
				x+=dx[i],y+=dy[i];
			}
		}
		if(end[s.x][s.y]==1) {
			printf("0");
			continue;
		}
		front=tail=1;
		q[1]=s;
		flag=0;
		while(front<=tail) {
			point u=q[front++];
			point v;
			for(int i=0;i<4;i++) {
				v.x=u.x+dx[i];
				v.y=u.y+dy[i];
				v.step=u.step+1;
				if(v.x<1 || v.x>n || v.y<1 || v.y>m) continue;
				if(maze[v.x][v.y]==0) continue;
				if(used[v.x][v.y]==1) continue;
				if(end[v.x][v.y]==1) {
					flag=1;
					front=tail+1;
					printf("%d\n",v.step);
					break;
				}
				used[v.x][v.y]=1;
				q[++tail]=v;
			}
		}
		if(flag==0) {
			printf("Poor Harry\n");
		}
		
	}
	return 0;
}

错了4,5,10三个点

2021/9/7 19:59
加载中...