P1126 机器人搬重物 bfs 坐标系
题目描述 https://www.luogu.org/problemnew/show/P1126
机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径$1.6米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个N \times MN×M的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：向前移动11步（Creep）；向前移动2步（Walk）；向前移动33步（Run）；向左转（Left）；向右转（Right）。每个指令所需要的时间为11秒。请你计算一下机器人完成任务所需的最少时间。
输入输出格式
输入格式：
第一行为两个正整数N,M(N,M \le 50)N,M(N,M≤50)，下面NN行是储藏室的构造，00表示无障碍，11表示有障碍，数字之间用一个空格隔开。接着一行有44个整数和11个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东EE，南SS，西WW，北NN），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。
输出格式：
一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出-1−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
说明，思路比较明朗，但是采坑无数
1. 建立坐标后，沿着x y递增是向右 向下的，和以最下角建立的坐标系不同
2. 机器人是有大小的，因此最外圈都是不能放机器人的，同时障碍的四个角都不能放
3 左西右东 我搞反了 悲催啊。
#include<stdio.h>
#include<functional>
#include<queue>
#include<vector>
#include<iostream>
#include<sstream>
#include<string.h>
#include<set>
using namespace std;
typedef struct {
int x,y;
int dir;
int il;
} node;
node start,last,tnode;
set<int> za; //又来存储障碍顶点
set<int> vs;// 存储处理过的状态，1000x+10y+dir
queue<node> que;
int n,m;
int N,M;
bool isgo=true;
int xx[]= {-1,0,1,0};
int yy[]= {0,1,0,-1};
bool existed(node t)
{
if(vs.count(1000*t.x+t.y*10+t.dir))
return true;
else
{
vs.insert(1000*t.x+t.y*10+t.dir);
return false;
}
}
void bfs() {
if(!isgo) return;
if(!que.empty())
{
tnode=que.front();
//cout<<tnode.x<<" "<<tnode.y<<" "<<tnode.dir<<" "<<tnode.il<<endl;
que.pop();
}
else
{
cout<<-1<<endl;
isgo=false;
return;
}
if(tnode.x==last.x&&tnode.y==last.y) {
cout<<tnode.il<<endl;
isgo=false;
return;
} else {
//处理左右
node t1=tnode;
t1.dir=(t1.dir-1+4)%4;
t1.il++;
if(!existed(t1))
que.push(t1);
node t2=tnode;
t2.dir=(t2.dir+1)%4;
t2.il++;
if(!existed(t2))
que.push(t2);
//在某个方向上走3步
int nx,ny;
bool iscango=false;
node t3=tnode;
{
nx=t3.x+xx[t3.dir];
ny=t3.y+yy[t3.dir];
if(nx>0&&nx<n&&ny>0&&ny<m&&!za.count(nx*M+ny)) {
t3.il++;
t3.x=nx;
t3.y=ny;
iscango=true;
if(!existed(t3))
que.push(t3);
}
}
node t4=tnode;
if(iscango) {
iscango=false;
nx=nx+xx[t4.dir];
ny=ny+yy[t4.dir];
if(nx>0&&nx<n&&ny>0&&ny<m&&!za.count(nx*M+ny)) {
t4.il++;
t4.x=nx;
t4.y=ny;
iscango=true;
if(!existed(t4))
que.push(t4);
}
}
node t5=tnode;
if(iscango) {
iscango=false;
nx=nx+xx[t5.dir];
ny=ny+yy[t5.dir];
if(nx>0&&nx<n&&ny>0&&ny<m&&!za.count(nx*M+ny)) {
t5.il++;
t5.x=nx;
t5.y=ny;
iscango=true;
if(!existed(t5))
que.push(t5);
}
}
//cout<<"size---"<<que.size()<<endl;
bfs();
}
}
int main() {
cin>>n>>m;
N=n+1;
M=m+1;
int t;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++) {
cin>>t;
if(t) {
if(!za.count(i*M+j))
za.insert(i*M+j);
if(!za.count(i*M+j+1))
za.insert(i*M+j+1);
if(!za.count((i+1)*M+j))
za.insert((i+1)*M+j);
if(!za.count((i+1)*M+j+1))
za.insert((i+1)*M+j+1);
}
}
cin>>start.x>>start.y;
cin>>last.x>>last.y;
char c;
cin>>c;
switch(c) {
case 'E':
start.dir=1;
break;
case 'S':
start.dir=2;
break;
case 'W':
start.dir=3;
break;
case 'N':
start.dir=0;
break;
}
start.il=0;
vs.insert(1000*start.x+10*start.y+start.dir);
que.push(start);
bfs();
}