1975: 機(jī)器人搬重物

?Time Limit:?1 Sec?????Memory Limit:?128 Mb?????Submitted:?64?????Solved:?10????

---

Description

機(jī)器人移動學(xué)會（RMI）現(xiàn)在正嘗試用機(jī)器人搬運物品。機(jī)器人的形狀是一個直徑1.6米的球。在試驗階段，機(jī)器人被用于在一個儲藏室中搬運貨物。儲藏室是一個N*M的網(wǎng)格，有些格子為不可移動的障礙。機(jī)器人的中心總是在格點上，當(dāng)然，機(jī)器人必須在最短的時間內(nèi)把物品搬運到指定的地方。機(jī)器人接受的指令有：向前移動1步（Creep）；向前移動2步（Walk）；向前移動3步（Run）；向左轉(zhuǎn)（Left）；向右轉(zhuǎn)（Right）。每個指令所需要的時間為1秒。請你計算一下機(jī)器人完成任務(wù)所需的最少時間。

Input

輸入的第一行為兩個正整數(shù)N,M（N,M<=50），下面N行是儲藏室的構(gòu)造，0表示無障礙，1表示有障礙，數(shù)字之間用一個空格隔開。接著一行有四個整數(shù)和一個大寫字母，分別為起始點和目標(biāo)點左上角網(wǎng)格的行與列，起始時的面對方向（東E，南S，西W，北N），數(shù)與數(shù)，數(shù)與字母之間均用一個空格隔開。終點的面向方向是任意的。

Output

一個整數(shù)，表示機(jī)器人完成任務(wù)所需的最少時間。如果無法到達(dá)，輸出-1。

Sample Input

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

Sample Output

12

Hint

Source

機(jī)器人搬重物

?

題意：給你一個圖，讓你求出機(jī)器人從一個點到另一個點需要的最短時間。乍一看就是普通的BFS求最短路問題。但是有很多坑。。。很多坑。。

　　　①首先機(jī)器人是在點上，障礙物是格子，也就是說機(jī)器人所在的點周圍的4個格子都不能有障礙物。而且點和格子的坐標(biāo)對應(yīng)關(guān)系要弄清楚，最好畫個圖。

　　　②然后行走分了方向，其實就是bfs多了兩個選擇，一個左轉(zhuǎn)一個右轉(zhuǎn)。

　　　③走的時候有直走1、2、3步三種方式，需要判斷前方有沒有障礙。

?

思路：進(jìn)行bfs，直接采用優(yōu)先隊列，這樣可以確定到達(dá)某一點時肯定是最短時間，不會因為轉(zhuǎn)向什么的產(chǎn)生影響。

　　　幾個特判的地方要注意：①起點終點一樣，0。②起點或終點在不可移動的地方，-1。

#include<cstdio> #include<queue> #include<cstring> using namespace std; const int maxn=55; char c; int a[maxn][maxn],n,m,sx,sy,ex,ey,sd; int dy[4]={1,0,-1,0}; int dx[4]={0,1,0,-1}; bool vis[maxn][maxn][5]; struct node {int x,y,d,step;//用d（0、1、2、3、4）表示不同朝向bool operator < (const node &a) const{return a.step<step;} }; priority_queue<node> q; //queue<node> q;bool check(int x,int y) {if(x>=n||y>=m||x<=0||y<=0)return false;if(a[x][y]==1||a[x+1][y]==1||a[x][y+1]==1||a[x+1][y+1]==1)return false;return true; }void bfs() {memset(vis,false,sizeof(vis));node now,next;now.x = sx;now.y = sy;now.d = sd;now.step = 0;if(!check(sx,sy)){printf("-1\n");return ;}if(!check(ex,ey)){printf("-1\n");return ;}while(!q.empty()) q.pop();q.push(now);vis[sx][sy][sd] = true;while(!q.empty()){now = q.top();q.pop();//printf("%d %d %d %d\n",now.x,now.y,now.d,now.step);if(now.x==ex&&now.y==ey){printf("%d\n",now.step);return ;}for(int step=1;step<=3;step++){next.x = now.x+dx[now.d]*step;next.y = now.y+dy[now.d]*step;next.d = now.d;if(check(next.x,next.y)&&vis[next.x][next.y][next.d]==false){next.step = now.step+1;q.push(next);vis[next.x][next.y][next.d] = true;}else//如果1 2 3某一個不能走，那后面的肯定不能走 {break;}}if(vis[now.x][now.y][(now.d+1)%4]==false)//óò×a {next.x = now.x;next.y = now.y;next.d = (now.d+1)%4;next.step = now.step+1;q.push(next);vis[next.x][next.y][next.d] = true;}if(vis[now.x][now.y][(now.d-1+4)%4]==false)//×ó×a {next.x = now.x;next.y = now.y;next.d = (now.d-1+4)%4;next.step = now.step+1;q.push(next);vis[next.x][next.y][next.d] = true;}}printf("-1\n"); } int main() {while(scanf("%d %d",&n,&m)!=EOF){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d\n",&a[i][j]);}}scanf("%d %d %d %d",&sx,&sy,&ex,&ey);getchar();scanf("%c",&c);if(sx==ex&&sy==ey){printf("0\n");continue;}if(c=='E') sd=0;else if(c=='S') sd=1;else if(c=='W') sd=2;else if(c=='N') sd=3;bfs();} }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/WWkkk/p/7348674.html

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的CSU-1975 机器人搬重物（BFS）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。