GitBook

这里写图片描述

需要注意坐标的对应 用了bfs

#include<stdio.h>
int map[9][9]= {
	0,0,1,1,1,1,1,1,1,
	1,0,0,1,0,0,1,0,1,
	1,0,0,1,1,0,0,0,1,
	1,0,1,0,1,1,0,1,1,
	1,0,0,0,0,1,0,0,1,
	1,1,0,1,0,1,0,0,1,
	1,1,0,1,0,1,0,0,1,
	1,1,0,1,0,0,0,0,1,
	0,1,1,1,1,1,1,0,0,
};
int e[10][10];
bool flag[10][10];
int inf=999999;
void bfs(int n,int m) {
	if(map[n][m]==1||n<0||m<0||n>=9||m>=9||flag[n][m])
		return;
	flag[n][m]=true;
	if(n+1<9&&map[n+1][m]==0) {
		if(e[n][m]<e[n+1][m])
			e[n+1][m]=e[n][m]+1;
		else if(e[n][m]>e[n+1][m]+1)
			e[n][m]=e[n+1][m]+1;
		bfs(n+1,m);
	}
	if(n-1>=0&&map[n-1][m]==0) {
		if(e[n][m]<e[n-1][m])
			e[n-1][m]=e[n][m]+1;
		else if(e[n][m]>e[n-1][m]+1)
			e[n][m]=e[n-1][m]+1;
		bfs(n-1,m);
	}
	if(m+1<9&&map[n][m+1]==0) {
		if(e[n][m]<e[n][m+1])
			e[n][m+1]=e[n][m]+1;
		else if(e[n][m]>e[n][m+1]+1)
			e[n][m]=e[n][m+1]+1;
		bfs(n,m+1);
	}
	if(m-1>=0&&map[n][m-1]==0) {
		if(e[n][m]<e[n][m-1])
			e[n][m-1]=e[n][m]+1;
		else if(e[n][m]>e[n][m-1]+1)
			e[n][m]=e[n][m-1]+1;
		bfs(n,m-1);
	}
}

int main() {
	int T;
	scanf("%d",&T);
	while(T--) {
		int x1,y1,x2,y2;
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		for(int i=0; i<9; i++) {
			for(int j=0; j<9; j++) {
				e[i][j]=inf;
				flag[i][j]=false;
			}
		}
		e[x2][y2]=0;
		bfs(x2,y2);
		if(e[x1][y1]==inf||map[x1][y1]==1)
			printf("LaoWang fail\n");
		else
			printf("%d\n",e[x1][y1]);
	}
	return 0;
}
//坐标给的好坑啊……
//还不如直接给n1,m1,n2,m2-.- 

题目地址:【HPU】[1737]老王特警队