求助BFS
查看原帖
求助BFS
117662
那一条变阻器楼主2020/8/25 15:17

只对了前两个点

#include <bits/stdc++.h>
using namespace std;
//0E东 y++ 1S南 x++ 2W西 x-- 3N北 y-- 
struct node{
	int x , y , ans , dir;
};
int n , m , sx , sy , tx , ty , sdir , f;
char sd;
int vis[60][60][10];
queue<node> q;
inline node work(int x , int y , int di , int tot , int step){
	while(step--){
		if(di == 0)
			if(!vis[x][y + 1][di] && y <= m) y++;
			else{
				f = 1;
				return (node){0 , 0 , 0 , 0};
			}
		if(di == 1)
			if(!vis[x + 1][y][di] && x <= n) x++;
			else{
				f = 1;
				return (node){0 , 0 , 0 , 0};
			}
		if(di == 2)
			if(!vis[x - 1][y][di] && x >= 1) x--;
			else{
				f = 1;
				return (node){0 , 0 , 0 , 0};
			}
		if(di == 3)
			if(!vis[x][y - 1][di] && y >= 1) y--;
			else{
				f = 1;
				return (node){0 , 0 , 0 , 0};
			}
	}
	vis[x][y][di] = 1;
	return (node){x , y , tot + 1 , di};
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++){
			scanf("%d" , &vis[i][j][0]);
			vis[i][j][1] = vis[i][j][2] = vis[i][j][3] = vis[i][j][0];
		}
	cin >> sx >> sy >> tx >> ty >> sd;
	if(sd == 'E') sdir = 0;
	if(sd == 'S') sdir = 1;
	if(sd == 'W') sdir = 2;
	if(sd == 'N') sdir = 3;
	q.push((node){sx , sy , 0 , sdir});
	vis[sx][sy][sdir] = 1;
	while(!q.empty()){
		node now = q.front() , pu;
		q.pop();
		if(now.x < 1 || now.x > n || now.y < 1 || now.y > m) continue;
		//getchar();
		if(now.x == tx && now.y == ty){
			cout << now.ans - 1;
			return 0;
		}
		//cout << now.x << " " << now.y << endl;
		//creep
		f = 0;
		pu = work(now.x , now.y , now.dir , now.ans , 1);
		if(!f) q.push(pu);
		//walk
		f = 0;
		pu = work(now.x , now.y , now.dir , now.ans , 2);
		if(!f) q.push(pu);
		//run
		f = 0;
		pu = work(now.x , now.y , now.dir , now.ans , 3);
		if(!f) q.push(pu);
		//left
		if(now.dir == 0 && !vis[now.x][now.y][3]) q.push((node){now.x , now.y , now.ans + 1 , 3}) , vis[now.x][now.y][3] = 1;
		if(now.dir == 1 && !vis[now.x][now.y][0]) q.push((node){now.x , now.y , now.ans + 1 , 0}) , vis[now.x][now.y][0] = 1;
		if(now.dir == 2 && !vis[now.x][now.y][1]) q.push((node){now.x , now.y , now.ans + 1 , 1}) , vis[now.x][now.y][1] = 1;
		if(now.dir == 3 && !vis[now.x][now.y][2]) q.push((node){now.x , now.y , now.ans + 1 , 2}) , vis[now.x][now.y][2] = 1;
		//right
		if(now.dir == 0 && !vis[now.x][now.y][1]) q.push((node){now.x , now.y , now.ans + 1 , 1}) , vis[now.x][now.y][1] = 1;
		if(now.dir == 1 && !vis[now.x][now.y][2]) q.push((node){now.x , now.y , now.ans + 1 , 2}) , vis[now.x][now.y][2] = 1;
		if(now.dir == 2 && !vis[now.x][now.y][3]) q.push((node){now.x , now.y , now.ans + 1 , 3}) , vis[now.x][now.y][3] = 1;
		if(now.dir == 3 && !vis[now.x][now.y][0]) q.push((node){now.x , now.y , now.ans + 1 , 0}) , vis[now.x][now.y][0] = 1;
	}
	cout << -1;
	return 0;
}
2020/8/25 15:17
加载中...