BOJ 1461

bfs搜索

转动平面相当于改变重力的方向

#include <cstdio>
#include <cstring>
#include <queue>
#define N 110
using namespace std;

struct line{
	int x0,y0,x1,y1;
	bool flag; //flag=1从左到右
}lines[N];

struct Point{
	int x,y,dir;
};

bool vis[N][N][4];
bool isin[N][N][4];
int dp[N][N][4]; //0表示重力向下 1表示重力向左...
int x0,y0,x1,y1;
int w,h,n;
int dir[4][2]={0,-1,-1,0,0,1,1,0};//二位数组按行存储（WA死了）

bool check(int x,int y){
	if(x>=0 && x<w && y>=0 && y<h)return 1;
	return 0;
}

int bfs(){                     //其实这里直接bfs搜即可，不用写成SPFA
	queue<Point>q;
	Point p1,p2;
	int i,j;
	memset(dp,-1,sizeof(dp));
	memset(isin,0,sizeof(isin));
	dp[x0][y0][0]=0;
	isin[x0][y0][0]=0;
	p1.x=x0,p1.y=y0,p1.dir=0,q.push(p1);
	while(!q.empty()){
		p1=q.front();
		q.pop();
		if(p1.x==x1 && p1.y==y1) return dp[x1][y1][p1.dir];
		int nowdir=(p1.dir+1)%4,x=p1.x,y=p1.y;
		while(check(x+dir[nowdir][0],y+dir[nowdir][1]) && !(x==x1 && y==y1) && !vis[x][y][nowdir]) x+=dir[nowdir][0],y+=dir[nowdir][1];
		if(dp[x][y][nowdir]==-1){
			dp[x][y][nowdir]=dp[p1.x][p1.y][p1.dir]+1;
			if(isin[x][y][nowdir]==0){
				p2.x=x,p2.y=y,p2.dir=nowdir;
				isin[x][y][nowdir]=1;
				q.push(p2);
			}
		}

		nowdir=(p1.dir+3)%4,x=p1.x,y=p1.y;
        while(check(x+dir[nowdir][0],y+dir[nowdir][1]) && !(x==x1 && y==y1) && !vis[x][y][nowdir]) x+=dir[nowdir][0],y+=dir[nowdir][1];
		if(dp[x][y][nowdir]==-1){
			dp[x][y][nowdir]=dp[p1.x][p1.y][p1.dir]+1;
			if(isin[x][y][nowdir]==0){
				p2.x=x,p2.y=y,p2.dir=nowdir;
				isin[x][y][nowdir]=1;
				q.push(p2);
			}
        }
		isin[p1.x][p1.y][p1.dir]=0;
	}
	return -1;
}

int main(){
	int t,T;
	int i,j;
	scanf("%d",&T);
	for(t=1;t<=T;t++){
		scanf("%d %d %d",&w,&h,&n);
		scanf("%d %d %d %d",&x0,&y0,&x1,&y1);
		memset(vis,0,sizeof(vis));
		for(i=1;i<=n;i++){
			scanf("%d %d %d %d",&lines[i].x0,&lines[i].y0,&lines[i].x1,&lines[i].y1);
			if(lines[i].x0==lines[i].x1){     // ==老写错
				for(j=lines[i].y0;j<lines[i].y1;j++) vis[lines[i].x0-1][j][3]=1,vis[lines[i].x0][j][1]=1;
			}
			else{
				for(j=lines[i].x0;j<lines[i].x1;j++) vis[j][lines[i].y0-1][2]=1,vis[j][lines[i].y0][0]=1;
			}
		}
		//for(j=0;j<w;j++) vis[0][j][0]=1,vis[h-1][j][2]=1;
		//for(j=0;j<h;j++) vis[j][0][1]=1,vis[j][w-1][3]=1;
		printf("%d\n",bfs());  
	} 
}