洛谷1126 机器人搬重物
题目描述
机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径1.6米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个N*M的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：向前移动1步（Creep）；向前移动2步（Walk）；向前移动3步（Run）；向左转（Left）；向右转（Right）。每个指令所需要的时间为1秒。请你计算一下机器人完成任务所需的最少时间。
输入输出格式
输入格式：
输入的第一行为两个正整数N,M（N,M<=50），下面N行是储藏室的构造，0表示无障碍，1表示有障碍，数字之间用一个空格隔开。接着一行有四个整数和一个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东E，南S，西W，北N），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。
输出格式：
一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出-1。
输入输出样例
输入样例#1：
9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 S
输出样例#1：
12
【思路】
BFS状态搜索。
思路简单，用x,y,dir,d描述状态信息，因为每个操作的时间均为1所以广搜最短路即可。
需要注意的是：
1、 因为机器人直径有1.6，所以用xy表示的机器人所占四个格子的左上角，因此机器人不能位于n行m列。
2、 判断一个行动是否可行不能只判断起始点，而应该判断整条路径，check_road。
【代码】
1 #include<iostream> 2 #include<cstring> 3 #include<queue> 4 #include<cstdlib> 5 #include<cmath> 6 using namespace std; 7 8 const int maxn = 50+5; 9 const char* dirs = "NESW"; 10 11 inline int dir_id(char c) { return strchr(dirs,c)-dirs; } 12 13 struct Node{ 14 int x,y,dir,d; 15 }; 16 17 inline void turn(Node& u,int t) { 18 if(t==1) {u.dir=(u.dir+3)%4; } 19 if(t==2) {u.dir=(u.dir+1)%4; } 20 } 21 22 int n,m,aim_x,aim_y,f_x,f_y; 23 char f_dir; 24 int G[maxn][maxn]; 25 int vis[maxn][maxn][4]; 26 queue<Node> q; 27 28 inline bool inside(int x,int y) { //nm不可达 29 return x>=1 && x<n && y>=1 && y<m && !G[x][y]&&!G[x+1][y]&&!G[x+1][y+1]&&!G[x][y+1]; 30 } 31 inline void if_print(int x,int y,int d) { 32 if(x==aim_x && y==aim_y) { cout<<d;exit(0); } 33 } 34 inline bool check_road(int fr_x,int fr_y,int e_x,int e_y) { //检查路径而不能只检查起始点 35 int dx=e_x-fr_x,dy=e_y-fr_y; 36 if(dx!=0) dx=dx/(abs(dx));if(dy!=0) dy=dy/(abs(dy)); 37 int x=fr_x,y=fr_y; 38 while(x!=e_x || y!=e_y) { 39 if(!inside(x,y)) return false; 40 x += dx; y += dy; 41 } 42 return inside(x,y); 43 } 44 void bfs() { 45 q.push((Node) {f_x,f_y,dir_id(f_dir),0}); 46 vis[f_x][f_y][dir_id(f_dir)]=1; 47 while(!q.empty()) { 48 Node u=q.front(); q.pop(); 49 int x=u.x,y=u.y,dir=u.dir,d=u.d; 50 Node u1=u; u1.d++; turn(u1,1); 51 if(!vis[x][y][u1.dir]) { vis[x][y][u1.dir]=1; q.push(u1); } 52 u1=u; u1.d++; turn(u1,2); 53 if(!vis[x][y][u1.dir]) { vis[x][y][u1.dir]=1; q.push(u1); } 54 55 for(int s=1;s<=3;s++) { 56 if(dir==0 && check_road(x,y,x-s,y) &&!vis[x-s][y][dir]) { 57 vis[x-s][y][dir]=1; q.push((Node) {x-s,y,dir,d+1}); if_print(x-s,y,d+1); 58 } 59 if(dir==1 && check_road(x,y,x,y+s) && !vis[x][y+s][dir]) { 60 vis[x][y+s][dir]=1; q.push((Node) {x,y+s,dir,d+1}); if_print(x,y+s,d+1); 61 } 62 if(dir==2 && check_road(x,y,x+s,y) && !vis[x+s][y][dir]) { 63 vis[x+s][y][dir]=1; q.push((Node) {x+s,y,dir,d+1}); if_print(x+s,y,d+1); 64 } 65 if(dir==3 && check_road(x,y,x,y-s) && !vis[x][y-s][dir]) { 66 vis[x][y-s][dir]=1; q.push((Node) {x,y-s,dir,d+1}); if_print(x,y-s,d+1); 67 } 68 } 69 } 70 } 71 72 int main() { 73 ios::sync_with_stdio(false); 74 cin>>n>>m; 75 for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>G[i][j]; 76 cin>>f_x>>f_y>>aim_x>>aim_y>>f_dir; 77 78 bfs(); 79 cout<<-1; 80 81 return 0; 82 }