练习题 - 机器人搬重物(图论)

前言

算法拾遗继续。

题目

问题描述

机器人移动学会(RMI)现在正尝试用机器人搬运物品。机器人的形状是一个直径1.6米的球。在试验阶段,机器人被用于在一个储藏室中搬运货物。储藏室是一个N*M的网格,有些格子为不可移动的障碍。机器人的中心总是在格点上,当然,机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有:向前移动1步(Creep);向前移动2步(Walk);向前移动3步(Run);向左转(Left);向右转(Right)。每个指令所需要的时间为1秒。请你计算一下机器人完成任务所需的最少时间。

输入(robot.in)

输入的第一行为两个正整数N,M(N,M<=50),下面N行是储藏室的构造,0表示无障碍,1表示有障碍,数字之间用一个空格隔开。接着一行有四个整数和一个大写字母,分别为起始点和目标点左上角网格的行与列,起始时的面对方向(东E,南S,西W,北N),数与数,数与字母之间均用一个空格隔开。终点的面向方向是任意的。

输出(robot.out)

一个整数,表示机器人完成任务所需的最少时间。如果无法到达,输出-1。

样例

robot.in

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

robot.out

12

解答

求解方法比较笨,记忆搜索。参照图论里面的BFS,从起点开始,对每种可以走的方法(向前1步、向前2步、向前3步、左转及右转)进行依次尝试,并记录到达各个点的时候使用的次数,到达过的点打标记,以免重复访问。

In my code implemetation

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int n, m, a[51][51] = {0}, tu[51][51] = {0}, dian[2][2], dui[10000][4] = {0},
          flag[2500][4] = {0};
int fw;
char fwt;
int top, tail;

int fforward(char c) {
  if (c == 'N')
    return (0);
  else if (c == 'E')
    return (1);
  else if (c == 'S')
    return (2);
  else // if (c == 'W')
    return (4);
}

void kuozhan(int x, int y) {
  int i, j;
  if (dui[top][1] == 0) { // towards N, north, currently

    // xiangqian 1 bu
    if ((x - 1 > 0) && (!tu[x - 1][y]) && (!flag[(x - 1 - 1) * m + y][dui[top][1]])) {
      dui[++tail][0] = (x - 1 - 1) * m + y;
      dui[tail][1] = dui[top][1];
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x - 1 - 1) * m + y][dui[top][1]] = 1;
      if ((x - 1 - 1) * m + y == (dian[1][0] - 1) * m + dian[1][1]) {
        printf("%d\n", dui[top][2] + 1);
        exit(0);
      }
    }

    // xiangqian 2 bu
    if ((x - 2 > 0) && (!tu[x - 1][y]) && (!tu[x - 2][y]) && (!flag[(x - 2 - 1) * m + y][dui[top][1]])) {
      dui[++tail][0] = (x - 2 - 1) * m + y;
      dui[tail][1] = dui[top][1];
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x - 2 - 1) * m + y][dui[top][1]] = 1;
      if ((x - 2 - 1) * m + y == (dian[1][0] - 1) * m + dian[1][1]) {
        printf("%d\n", dui[top][2] + 1);
        exit(0);
      }
    }

    // xiangqian 3 bu
    if ((x - 3 > 0) && (!tu[x - 1][y]) && (!tu[x - 2][y]) && (!tu[x - 3][y]) && (!flag[(x - 3 - 1) * m + y][dui[top][1]])) {
      dui[++tail][0] = (x - 3 - 1) * m + y;
      dui[tail][1] = dui[top][1];
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x - 3 - 1) * m + y][dui[top][1]] = 1;
      if ((x - 3 - 1) * m + y == (dian[1][0] - 1) * m + dian[1][1]) {
        printf("%d\n", dui[top][2] + 1);
        exit(0);
      }
    }

    // zuozhuan
    if (!flag[(x - 1) * m + y][(dui[top][1] - 1) % 4]) {
      dui[++tail][0] = (x - 1) * m + y;
      dui[tail][1] = (dui[top][1] - 1) % 4;
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x - 1) * m + y][(dui[top][1] - 1) % 4] = 1;
    }

    // youzhuan
    if (!flag[(x - 1) * m + y][(dui[top][1] + 1) % 4]) {
      dui[++tail][0] = (x - 1) * m + y;
      dui[tail][1] = (dui[top][1] + 1) % 4;
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x - 1) * m + y][(dui[top][1] + 1) % 4] = 1;
    }

  } else if (dui[top][1] == 1) { // towards E, east, currently

    // xiangqian 1 bu
    if ((y + 1 < m) && (!tu[x][y + 1]) && (!flag[(x - 1) * m + y + 1][dui[top][1]])) {
      dui[++tail][0] = (x - 1) * m + y + 1;
      dui[tail][1] = dui[top][1];
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x - 1) * m + y + 1][dui[top][1]] = 1;
      if ((x - 1) * m + y + 1 == (dian[1][0] - 1) * m + dian[1][1]) {
        printf("%d\n", dui[top][2] + 1);
        exit(0);
      }
    }

    // xiangqian 2 bu
    if ((y + 2 < m) && (!tu[x][y + 1]) && (!tu[x][y + 2]) && (!flag[(x - 1) * m + y + 2][dui[top][1]])) {
      dui[++tail][0] = (x - 1) * m + y + 2;
      dui[tail][1] = dui[top][1];
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x - 1) * m + y + 2][dui[top][1]] = 1;
      if ((x - 1) * m + y + 2 == (dian[1][0] - 1) * m + dian[1][1]) {
        printf("%d\n", dui[top][2] + 1);
        exit(0);
      }
    }

    // xianqian 3 bu
    if ((y + 3 < m) && (!tu[x][y + 1]) && (!tu[x][y + 2]) && (!tu[x][y + 3]) && (!flag[(x - 1) * m + y + 3][dui[top][1]])) {
      dui[++tail][0] = (x - 1) * m + y + 3;
      dui[tail][1] = dui[top][1];
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x - 1) * m + y + 3][dui[top][1]] = 1;
      if ((x - 1) * m + y + 3 == (dian[1][0] - 1) * m + dian[1][1]) {
        printf("%d\n", dui[top][2] + 1);
        exit(0);
      }
    }

    // zuozhuan
    if (!flag[(x - 1) * m + y][(dui[top][1] - 1) % 4]) {
      dui[++tail][0] = (x - 1) * m + y;
      dui[tail][1] = (dui[top][1] - 1) % 4;
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x - 1) * m + y][(dui[top][1] - 1) % 4] = 1;
    }

    // youzhuan
    if (!flag[(x - 1) * m + y][(dui[top][1] + 1) % 4]) {
      dui[++tail][0] = (x - 1) * m + y;
      dui[tail][1] = (dui[top][1] + 1) % 4;
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x - 1) * m + y][(dui[top][1] + 1) % 4] = 1;
    }
  } else if (dui[top][1] == 2) { // towards S, south, currently

    // xianqian 1 bu
    if ((x + 1 < n) && (!tu[x + 1][y]) && (!flag[(x + 1 - 1) * m + y][dui[top][1]])) {
      dui[++tail][0] = (x + 1 - 1) * m + y;
      dui[tail][1] = dui[top][1];
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x + 1 - 1) * m + y][dui[top][1]] = 1;
      if ((x + 1 - 1) * m + y == (dian[1][0] - 1) * m + dian[1][1]) {
        printf("%d\n", dui[top][2] + 1);
        exit(0);
      }
    }

    // xiangqian 2 bu
    if ((x + 2 < n) && (!tu[x + 1][y]) && (!tu[x + 2][y]) && (!flag[(x + 2 - 1) * m + y][dui[top][1]])) {
      dui[++tail][0] = (x + 2 - 1) * m + y;
      dui[tail][1] = dui[top][1];
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x + 2 - 1) * m + y][dui[top][1]] = 1;
      if ((x + 2 - 1) * m + y == (dian[1][0] - 1) * m + dian[1][1]) {
        printf("%d\n", dui[top][2] + 1);
        exit(0);
      }
    }

    // xiangqian 3 bu
    if ((x + 3 < n) && (!tu[x + 1][y]) && (!tu[x + 2][y]) && (!tu[x + 3][y]) && (!flag[(x + 3 - 1) * m + y][dui[top][1]])) {
      dui[++tail][0] = (x + 3 - 1) * m + y;
      dui[tail][1] = dui[top][1];
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x + 3 - 1) * m + y][dui[top][1]] = 1;
      if ((x + 3 - 1) * m + y == (dian[1][0] - 1) * m + dian[1][1]) {
        printf("%d\n", dui[top][2] + 1);
        exit(0);
      }
    }

    // zuozhuan
    if (!flag[(x - 1) * m + y][(dui[top][1] - 1) % 4]) {
      dui[++tail][0] = (x - 1) * m + y;
      dui[tail][1] = (dui[top][1] - 1) % 4;
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x - 1) * m + y][(dui[top][1] - 1) % 4] = 1;
    }

    // youzhuan
    if (!flag[(x - 1) * m + y][(dui[top][1] + 1) % 4]) {
      dui[++tail][0] = (x - 1) * m + y;
      dui[tail][1] = (dui[top][1] + 1) % 4;
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x - 1) * m + y][(dui[top][1] + 1) % 4] = 1;
    }
  } else if (dui[top][1] == 3) { // towards W, west, currently

    // xianqian 1 bu
    if ((y - 1 > 0) && (!tu[x][y - 1]) && (!flag[(x - 1) * m + y - 1][dui[top][1]])) {
      dui[++tail][0] = (x - 1) * m + y - 1;
      dui[tail][1] = dui[top][1];
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x - 1) * m + y - 1][dui[top][1]] = 1;
      if ((x - 1) * m + y - 1 == (dian[1][0] - 1) * m + dian[1][1]) {
        printf("%d\n", dui[top][2] + 1);
        exit(0);
      }
    }

    // xiangqian 2 bu
    if ((y - 2 > 0) && (!tu[x][y - 1]) && (!tu[x][y - 2]) && (!flag[(x - 1) * m + y - 2][dui[top][1]])) {
      dui[++tail][0] = (x - 1) * m + y - 2;
      dui[tail][1] = dui[top][1];
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x - 1) * m + y - 2][dui[top][1]] = 1;
      if ((x - 1) * m + y - 2 == (dian[1][0] - 1) * m + dian[1][1]) {
        printf("%d\n", dui[top][2] + 1);
        exit(0);
      }
    }

    // xiangqian 3 bu
    if ((y - 3 > 0) && (!tu[x][y - 1]) && (!tu[x][y - 2]) && (!tu[x][y - 3]) && (!flag[(x - 1) * m + y - 3][dui[top][1]])) {
      dui[++tail][0] = (x - 1) * m + y - 3;
      dui[tail][1] = dui[top][1];
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x - 1) * m + y - 3][dui[top][1]] = 1;
      if ((x - 1) * m + y - 3 == (dian[1][0] - 1) * m + dian[1][1]) {
        printf("%d\n", dui[top][2] + 1);
        exit(0);
      }
    }

    // zuozhuan
    if (!flag[(x - 1) * m + y][(dui[top][1] - 1) % 4]) {
      dui[++tail][0] = (x - 1) * m + y;
      dui[tail][1] = (dui[top][1] - 1) % 4;
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x - 1) * m + y][(dui[top][1] - 1) % 4] = 1;
    }

    // youzhuan
    if (!flag[(x - 1) * m + y][(dui[top][1] + 1) % 4]) {
      dui[++tail][0] = (x - 1) * m + y;
      dui[tail][1] = (dui[top][1] + 1) % 4;
      dui[tail][2] = dui[top][2] + 1;
      dui[tail][3] = top;
      flag[(x - 1) * m + y][(dui[top][1] + 1) % 4] = 1;
    }
  }

  top++;
}

void fsearch(int x, int y, int f, int s) {
  if (x == dian[1][0] && y == dian[1][1]) {
    printf("%d\n", s);
    exit(0);
  } else {
    top = 0;
    tail = 0;

    dui[top][0] = (x - 1) * m + y;
    dui[top][1] = f;
    dui[top][2] = s;
    flag[(x - 1) * m + y][f] = 1;

    while (top <= tail) {
      kuozhan(dui[top][0] / m + 1, dui[top][0] % m);
    }
  }
}

int main() {
  scanf("%d%d", &n, &m);
  int i, j;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++) {
      scanf("%d", &a[i][j]);
      if (a[i][j] == 1)
        tu[i - 1][j - 1] = tu[i][j - 1] = tu[i - 1][j] = tu[i][j] = 1;
    }

  for (j = 0; j <= m; j++) {
    tu[0][j] = 1;
    tu[n][j] = 1;
  }

  for (i = 0; j <= n; j++) {
    tu[i][0] = 1;
    tu[i][m] = 1;
  }

  scanf("%d%d%d%d", &dian[0][0], &dian[0][1], &dian[1][0], &dian[1][1]);
  scanf(" %c", &fwt);

  fw = fforward(fwt);

  if (dian[1][0] == 0 || dian[1][0] == n || dian[1][1] == 0 || dian[1][1] == m)
    printf("%d\n", -1);
  else if (dian[0][0] == 0 || dian[0][0] == n || dian[0][1] == 0 || dian[0][1] == m)
    printf("%d\n", -1);
  else if (tu[dian[0][0]][dian[0][1]] || tu[dian[1][0]][dian[1][1]])
    printf("%d\n", -1);
  else {
    fsearch(dian[0][0], dian[0][1], fw, 0);

    // for (j = 0; j < 4; j++) {
    //   for (i = 1; i < top; i++)
    //     printf("%2d ", dui[i][j]);
    //   putchar('\n');
    // }
    // getchar();

    printf("%d\n", -1);
  }

  return 0;
}

在洛谷上测试,通过率80%,有两组数据没有通过。(其中一组,我的输出为6,正确为4;另外一组我的输出为-1,正确为32。由于我不能下载数据,所以没办法进一步debug。个人猜想可能是因为代码太冗长,中间过程出现了一个错误。以后有时间再来修改吧。)

参考


* cached version, generated at 2018-12-07 05:51:10 UTC.

Subscribe by RSS