洛谷 P1126 机器人搬重物

题目传送门

解题思路:

一道bfs,但本题有几个坑点.

1.题目给的图并不是最终可以用的图,要先手动转换成格点图.

2.机器人有一个直径,则说明原题给的图的障碍的四个节点都不能走.

3.接2,图的四周不能走,因为走的话机器人的一部分会出图.

4.机器人只能左转或右转,向后转需要两个时间.

其实解决了坑点,代码还是很好写的.

AC代码:

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<queue>
  4 #include<cmath>
  5 #include<map>
  6 
  7 using namespace std;
  8 
  9 int n,m,a[54][54],x2,y2,x1,y11,tot;
 10 int tox[4][3] = {-1,-2,-3,0,0,0,1,2,3,0,0,0}; 
 11 int toy[4][3] = {0,0,0,-1,-2,-3,0,0,0,1,2,3};
 12 bool vis[54][54][4],ok[4][4] = {{0,1,0,1},{1,0,1,0},{0,1,0,1},{1,0,1,0}};
 13 //ok用来判断是不是向左或向右转 
 14 char o;
 15 map<char,int> pp;
 16 map<int,char> dp;
 17 struct kkk{
 18     int xx,yy,time;
 19     char way;
 20 }e[126001];
 21 queue<kkk> q;
 22 
 23 inline bool bfs(int x,int y) {
 24     vis[x][y][pp[o]] = 1;
 25     e[++tot].xx = x;
 26     e[tot].yy = y;
 27     e[tot].way = o;
 28     e[tot].time = 0;
 29     q.push(e[tot]);
 30     while(!q.empty()) {
 31         kkk k = q.front();
 32         q.pop();
 33         if(k.xx == x2 && k.yy == y2) {
 34             printf("%d",k.time);
 35             return false;
 36         }
 37         for(int i = 0;i <= 3; i++) {
 38             if(i == pp[k.way]) {
 39                 for(int j = 0;j <= 2; j++) {
 40                     int tx = k.xx + tox[i][j];
 41                     int ty = k.yy + toy[i][j];
 42                     if(tx < 1 || tx >= n || ty < 1 || ty >= m) break;
 43                     if(a[tx][ty] == 1) break;
 44                     if(!vis[tx][ty][i]) {
 45                         vis[tx][ty][i] = 1;
 46                         e[++tot].xx = tx;
 47                         e[tot].yy = ty;
 48                         e[tot].time = k.time + 1;
 49                         e[tot].way = k.way;
 50                         q.push(e[tot]);
 51                     }
 52                 }
 53             }
 54             else {
 55                 if(ok[pp[k.way]][i] == 1 && !vis[k.xx][k.yy][i]) {
 56                     vis[k.xx][k.yy][i] = 1;
 57                     e[++tot].way = dp[i];
 58                     e[tot].time = k.time + 1;
 59                     e[tot].xx = k.xx;
 60                     e[tot].yy = k.yy;
 61                     q.push(e[tot]);
 62                 }
 63             }
 64         }
 65     }
 66     return true;
 67 }
 68 
 69 inline void chushimap() {
 70     pp['N'] = 0;
 71     pp['W'] = 1;
 72     pp['S'] = 2;
 73     pp['E'] = 3;
 74     dp[0] = 'N';
 75     dp[1] = 'W';
 76     dp[2] = 'S';
 77     dp[3] = 'E';
 78 }
 79 
 80 int main() {
 81     scanf("%d%d",&n,&m);
 82     for(int i = 1;i <= n; i++)
 83         for(int j = 1;j <= m; j++) {
 84             int ooo;
 85             scanf("%d",&ooo);
 86             if(ooo == 1) {
 87                 a[i][j] = 1;
 88                 a[i][j-1] = 1;
 89                 a[i-1][j] = 1;
 90                 a[i-1][j-1] = 1;
 91             }
 92         }
 93     scanf("%d%d%d%d",&x1,&y11,&x2,&y2);
 94     cin >> o;
 95     chushimap();
 96 //    for(int i = 1;i <= n+1; i++) {//格点图生成器 
 97 //        for(int j = 1;j <= m+ 1; j++)
 98 //            cout << a[i][j] << ' ';
 99 //        cout << endl;
100 //    }
101     if(bfs(x1,y11))
102         printf("-1");
103     
104     return 0;
105 }