求调,代码有注释,样例已过
查看原帖
求调,代码有注释,样例已过
1100140
Ryoo楼主2024/8/9 09:25

前十一个测试点wa最后一个re

#include <bits/stdc++.h>
using namespace std;
int bfs[16388][3],min,dir[5][2] = {{0,0},{0,-1},{1,0},{0,1},{-1,0}};
char a[2000][2000],b[2000][2000];		//b数组中,0表示障碍,1表示可通行,2表示终点,3表示已遍历过的部分 
int main() {
	
	////////////////////////////////////////信息输入 
	int n,m,hx[515],hy[515],medalx[515],medaly[515];
	scanf("%d%d", &n,&m);
	getchar();
	
	for(int i = 1; i <= n; i++) 
		for(int j = 1; j <= m; j++) b[i][j] = '1';
	
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m;j++) {
			scanf("%c", &a[i][j]);
			if(a[i][j] == 'X') b[i][j] = '0';
		}
		getchar();
	}
	int coun=0;
	 for(int i = 1; i <= 512; i++) {
	 	int t1,t2,t3,t4;
	 	scanf("%d%d%d%d", &t1,&t2,&t3,&t4);
	 	if(t1==0&&t2==0&&t3==0&&t4==0) {
		 	coun = i-1;
		 	break;
		 }
	 		
	 	else {
	 		hx[i] = t4; hy[i] = t3; medalx[i] = t2; medaly[i] = t1;
		 }
	 }
	 ///////////////////////////////////////////////// 
	 


	 for(int i = 1; i <= coun; i++) {
	 	b[medaly[i]][medalx[i]] = '2';
	 	if(hx[i] == medalx[i] && hy[i] == medaly[i]) {
		 	printf("0");continue;
		 }
	 //	for(int j = 1; j <= m; j++) if(b[medaly[i]][j]!='0') b[medaly[i]][j] = '2';
	 //	for(int j = 1; j <= n; j++) if(b[j][medalx[i]]!='0') b[j][medalx[i]] = '2';
	 	//int tx=medalx[i],ty=medaly[i];
	 	int pd[9] = {1,1,1,1,1,1,1,1,1};		//坐标1-8表示上下左右,下右,下左,上左,上右是否碰到障碍物的标志 
	 	
	 	//将可以看到奖杯的坐标标记 
	 	 for(int j = 1; j <= max(n,m); j++) {
	 		if(medaly[i]-j>=1 && b[medaly[i]-j][medalx[i]]!='0' && pd[1] != 0) b[medaly[i]-j][medalx[i]] = '2';			 
	 		else pd[1] = 0;
	 		if(medaly[i]+j<=n && b[medaly[i]+j][medalx[i]]!='0' && pd[2] != 0) b[medaly[i]+j][medalx[i]] = '2';
	 		else pd[2] = 0;
	 		if(medalx[i]-j>=1 && b[medaly[i]][medalx[i]-j]!='0' && pd[3] != 0) b[medaly[i]][medalx[i]-j] = '2';
	 		else pd[3] = 0;
	 		if(medalx[i]+j<=m && b[medaly[i]][medalx[i]+j]!='0' && pd[4] != 0) b[medaly[i]][medalx[i]+j] = '2';
			else pd[4] = 0;
	 		
	 		if(medalx[i]+j<=m && medaly[i]+j<=n && b[medaly[i]+j][medalx[i]+j] != '0' && pd[5] != 0) b[medaly[i]+j][medalx[i]+j] = '2';
	 		else pd[5] = 0;
	 		if(medalx[i]-j>=1 && medaly[i]+j<=n && b[medaly[i]+j][medalx[i]-j] != '0' && pd[6] != 0) b[medaly[i]+j][medalx[i]-j] = '2';
	 		else pd[6] = 0;
	 		if(medalx[i]-j>=1 && medaly[i]-j>=1 && b[medaly[i]-j][medalx[i]-j] != '0' && pd[7] != 0) b[medaly[i]-j][medalx[i]-j] = '2';
	 		else pd[7] = 0;
			if(medalx[i]+j<=m && medaly[i]-j>=1 && b[medaly[i]-j][medalx[i]+j] != '0' && pd[8] != 0) b[medaly[i]-j][medalx[i]+j] = '2';
			else pd[8] = 0;
		 }
		 
		 
		 int head = 0,tail = 1,pdget = 0;	//pdget用于判断是否到达过能看到奖杯的地方 
		 bfs[1][0] = hx[i];bfs[1][1] = hy[i];
		 
		 do {
		 	head++;
		 	for(int i = 1; i <= 4; i++) {
		 	   	int x = bfs[head][0]+dir[i][0],y = bfs[head][0]+dir[i][1];
			 	if(x >= 1 && x <= m && y >= 1 && y <= n && b[y][x] != '0' && b[y][x] != '3') {
			 	 	tail++;bfs[tail][0] = x; bfs[tail][1] = y;bfs[tail][2] += 1;
					
					if(b[y][x] == '2') {		//到达能看到奖杯的地方 
						printf("%d\n", bfs[tail][2]);
						head=tail;	//找到最短路经,跳出while循环 
						pdget = 1;
						break;
					}
					b[y][x] = '3'; 		 		
				 }
			 }
		 }while(head<tail);
		 if(!pdget) printf("Poor Harry\n");
		 
		 //重置b数组 
		 for(int i = 1; i <= n; i++) {
		 	for(int j = 1; j <= m; j++) {
		 		//printf("%c ", b[i][j]);
		 		if(b[i][j] == '2' || b[i][j] == '3') b[i][j] = '1';
		 		
			 }
			 //printf("\n");
		 }
	 }
	return 0;
}
2024/8/9 09:25
加载中...