P2199手打队列70分求助
查看原帖
P2199手打队列70分求助
723171
fqEason楼主2022/9/3 13:01

70分:

#include <bits/stdc++.h>
using namespace std;
int dx[5]={1,-1,0,0};
int dy[5]={0,0,1,-1};
int nx,ny;
char a[8385][8385];
bool vis[8385][8385];
struct node{
	int x;
	int y;
	int step;
}b[16385];
int sx,sy,ex,ey;
int n,m;
int fx[10]={1,-1,0,0,1,-1,-1,1};
int fy[10]={0,0,1,-1,1,-1,1,-1};
bool check(int x, int y, int l, int r) {
	if (x==l&&y==r) return true;
	for (int i=0;i<=7;i++) {
		int nx=x,ny=y;
		while(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]=='O') {
			if (nx==l&&ny==r) return true;
			nx+=fx[i];
			ny+=fy[i];	
		}
	}
	return false;
}
void bfs(int x, int y){
	memset(vis,false,sizeof(vis));
	memset(b,0,sizeof(b));
	int h,t;
	h=t=1;
	b[h].x=x;
	b[h].y=y;
	vis[x][y]=true;
	if (check(x,y,ex,ey)) {
		cout << "0\n";
	}
	while(h<=t) {
		for (int i=0;i<=3;i++) {
			nx=b[h].x+dx[i];
			ny=b[h].y+dy[i];
			if (check(nx,ny,ex,ey)) {
				cout << b[h].step+1 << endl;
				return ;
			}
			if (nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny]&&a[nx][ny]=='O') {
				b[++t].x=nx;
				b[t].y=ny;
				b[t].step=b[h].step+1;
				vis[nx][ny]=true;
			}
		}
		h++;
	}
	cout << "Poor Harry\n";
}
int main() {
	cin >> n >> m;
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			cin >> a[i][j];
		}
	}
	while(cin >> ex >> ey >> sx >> sy) {
		if (!sx&&!sy&&!ex&&!ey)return 0;
		bfs(sx,sy);
	}
	return 0;
}

0分:

#include <bits/stdc++.h>
using namespace std;
int dx[5]={1,-1,0,0};
int dy[5]={0,0,1,-1};
int nx,ny;
char a[5385][5385];
bool vis[5385][5385];
struct node{
	int x;
	int y;
	int step;
}b[16385];
int sx,sy,ex,ey;
int n,m;
int fx[10]={1,-1,0,0,1,-1,-1,1};
int fy[10]={0,0,1,-1,1,-1,1,-1};
bool check(int x, int y, int l, int r) {
	if (x==l&&y==r) return true;
	for (int i=0;i<=7;i++) {
		int nx=x+fx[i],ny=y+fy[i];
		while(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]=='O') {
			if (nx==l&&ny==r) return true;	
			nx+=fx[i];
			ny+=fy[i];
		}
	}
	return false;
}
void bfs(int x, int y){
	memset(vis,false,sizeof(vis));
	memset(b,0,sizeof(b));
	int h,t;
	h=t=1;
	b[h].x=x;
	b[h].y=y;
	vis[x][y]=true;
	if (check(x,y,ex,ey)) {
		cout << "0\n";
	}
	while(h<=t) {
		for (int i=0;i<=3;i++) {
			nx=b[h].x+dx[i];
			ny=b[h].y+dy[i];
			if (check(nx,ny,ex,ey)) {
				cout << b[h].step+1 << endl;
				return ;
			}
			if (nx>=1&&nx<=n&&ny>=1&&ny<=m&&!vis[nx][ny]&&a[nx][ny]=='O') {
				b[++t].x=nx;
				b[t].y=ny;
				b[t].step=b[h].step+1;
				vis[nx][ny]=true;
			}
		}
		h++;
	}
	cout << "Poor Harry\n";
}
int main() {
	cin >> n >> m;
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			cin >> a[i][j];
		}
	}
	while(cin >> ex >> ey >> sx >> sy) {
		if (!sx&&!sy&&!ex&&!ey)return 0;
		bfs(sx,sy);
	}
	return 0;
}
2022/9/3 13:01
加载中...