Uva 816 Abbott's Revenge(BFS)

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std; struct Node
{
int row,col,dir;
Node(int row=,int col=,int dir=):row(row),col(col),dir(dir) {}
}; const char * dirs="NESW";
const char * turns="FLR";
const int maxn=; int have_way[maxn][maxn][][];///进入方向最多有4个,转弯方向最多有3个,最多是9*9的迷宫
int visit[maxn][maxn][];///0为起点,-1表示未被访问,1表示路径中的点
Node pre[maxn][maxn][];
int row0,col0, dir, row1, col1, row2, col2; int dir_id(char c)
{
return strchr(dirs, c) - dirs;
} int turn_id(char c)
{
return strchr(turns, c) - turns;
} const int dirrow[] = {-, , , };
const int dircol[] = {, , , -}; bool input()
{
char s[],s2[];
if(scanf("%s%d%d%s%d%d", s, &row0, &col0, s2, &row2, &col2) != ) return false;///输入初始位置
printf("%s\n", s); dir=dir_id(s2[]);
row1 = row0 + dirrow[dir];
col1 = col0 + dircol[dir]; memset(have_way,,sizeof(have_way));
for(;;)
{
int row, col;
scanf("%d",&row);
if(row==) break;
scanf("%d",&col);
while(scanf("%s",s)==&&s[]!='*')
{
for(int i=; i<strlen(s); i++)
have_way[row][col][dir_id(s[])][turn_id(s[i])]=;///输入每个点的进入方向及通行方向
}
}
return true;
} bool inside(int row,int col)
{
return row >= && row <= && col >= && col <= ;
} Node walk(Node t,int turn)
{
int dir=t.dir;
if(turn ==) dir = (dir+)%;///按顺时针+3就是对应的转弯方向,即是向右
if(turn==) dir=(dir+)%;///按顺时针+3就是对应的转弯方向,即是向左
return Node(t.row+dirrow[dir],t.col+dircol[dir],dir);
} void print(Node u)
{
vector<Node> nodes;/// 从目标结点逆序追溯到初始结点
for(;;)
{
nodes.push_back(u);
if(visit[u.row][u.col][u.dir]==) break;
u=pre[u.row][u.col][u.dir];
}
nodes.push_back(Node(row0,col0,dir));
int cnt = ;
for(int i = nodes.size()-; i >= ; i--)/// 打印解,每行10个
{
if(cnt % == ) printf(" ");
printf(" (%d,%d)", nodes[i].row, nodes[i].col);
if(++cnt % == ) printf("\n");
}
if(nodes.size() % != ) printf("\n");
} void run()
{
queue<Node> q;
memset(visit,-,sizeof(visit));
Node u(row1, col1, dir);
visit[u.row][u.col][u.dir]=;
q.push(u);
while(!q.empty())
{
Node u=q.front();
q.pop();
if(u.row == row2 && u.col == col2)///到达边界
{
print(u);
return;
}
for(int i = ; i < ; i++)///0~2表示前行,右转,左转
{
Node v = walk(u, i);
if(have_way[u.row][u.col][u.dir][i] && inside(v.row, v.col) && visit[v.row][v.col][v.dir] < )
{
visit[v.row][v.col][v.dir] = visit[u.row][u.col][u.dir] + ;
pre[v.row][v.col][v.dir] = u;///记录前驱
q.push(v);
}
}
}
printf(" No Solution Possible\n");
} int main()
{
while(input())
{
run();
}
return ;
}
上一篇:使用SPM创建新组件


下一篇:SharePoint固定的Footer