• 欢迎光临~

# 6.4.2 用BFS求最短路

Abbott's_Revenge题解

``````#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;

const int maxl = 11;

const int maxword = 20+5;
int toward[4][2] = {-1,0,0,1,1,0,0,-1}, dic[maxl][maxl][4][3];

struct Point{
int x, y;
Point(int x = 0, int y = 0) : x(x), y(y) {}
};

struct Node{
int x, y, from;//0 1 2 3 nesw 012 go l f r
vector<Point> v[4];
}node[maxl][maxl];

int main() {
//	freopen("test.in", "r", stdin);
//	freopen("test.out", "w", stdout);
char name[maxword];
while(scanf("%s", name) == 1 && strcmp(name, "END")) {
int sx, sy, ex, ey;
char sdic;
cin >> sx >> sy >> sdic >> ex >> ey;
memset(node, 0, sizeof(node));
memset(dic, 0, sizeof(dic));
int tx, ty;
while(scanf("%d", &tx) == 1 && tx) {
scanf("%d", &ty);
node[tx][ty].x = tx;
node[tx][ty].y = ty;
char buf[10];
while(scanf("%s", buf)==1 && strcmp(buf, "*")) {
int d;
switch(buf[0]) {
case 'N': d=0; break;
case 'E': d=1; break;
case 'S': d=2; break;
case 'W': d=3; break;
default: break;
}
for(int i = 1; i < strlen(buf); i++) {
switch(buf[i]) {
case 'L': dic[tx][ty][d][0] = 1; break;
case 'F': dic[tx][ty][d][1] = 1; break;
case 'R': dic[tx][ty][d][2] = 1; break;
default : break;
}
}
}
}
int d;
switch(sdic) {
case 'N': d=0; break;
case 'E': d=1; break;
case 'S': d=2; break;
case 'W': d=3; break;
default: break;
}
dic[sx][sy][d][1] = 0;
int sx1 = sx+toward[d][0], sy1 = sy+toward[d][1];
node[sx1][sy1].x = sx1;
node[sx1][sy1].y = sy1;
node[sx1][sy1].v[d].push_back(Point(sx, sy));
node[sx1][sy1].v[d].push_back(Point(sx1, sy1));
node[sx1][sy1].from = d;
queue<Node> q;
q.push(node[sx1][sy1]);
vector<Point> ans;
while(!q.empty()) {
Node n = q.front();
q.pop();
if(n.x == ex && n.y == ey) {
ans = n.v[n.from];
break;
}
int temp = n.from;
for(int i = 0; i < 3; i++) {
if(dic[n.x][n.y][temp][i]) {
int ndis = (temp+4+i-1)%4, sum = 10;
int px = n.x+toward[ndis][0], py = n.y+toward[ndis][1];
//			  for(int j = 0; j < 3; j++) {
//			  	sum += dic[px][py][ndis][j];
//			  }
if(sum) {
Node insert;
insert.x = px;
insert.y = py;
insert.from = ndis;
insert.v[ndis] = n.v[n.from];
insert.v[ndis].push_back(Point(px, py));
q.push(insert);
}
dic[n.x][n.y][temp][i] = 0;
}
}
}
cout << name << endl;
if(ans.empty()) cout << "  No Solution Possible" << endl;
else{
for(int i = 0; i < ans.size(); i++) {
if(i%10 == 0) cout << "  ";
cout << "(" << ans[i].x << "," << ans[i].y << ")";
if(i%10 == 9) cout << endl;
else if(i != ans.size()-1) cout << " ";
}
if(ans.size()%10) cout << endl;
}
}
return 0;
}
``````