练习题 - 那二十三个拐角(动态规划)

前言

算法拾遗继续。

题目

问题描述

故事的起源不加赘述,那 23 个路口。 
单刀直入,我直接说题的意思。

蚊子和疯子在做一件事,就是他们要在茫茫的大街上找一个出发点,然后从出发点开始,经过上下左右 23 次拐弯,到达一个他们也不知道的地方。

老城的街道排列的十分有规律,于是疯子和蚊子把老城的街道排布画在了一张地图上。地图上每一个点代表一个地方,而这个地方有一定的憧憬值,疯子希望可以带蚊子走过的二十三个路口的憧憬值总和是所有方案中最大的。

现在我们读入一个矩阵,如果此点为 0,则这个点为起点,如果此点为-1,则这个点为障碍点,否则这个数代表憧憬值。注意起点和障碍点是没有憧憬值的,起点只有开始的时候可以达到,不可以再回来。而障碍点根本就不可以走过。这样一来,请你选择合适的路线,使走完 23 个路口后得到最大的憧憬值,有憧憬值的点可以重复进出,每次可以选择四个方向,上下左右。起点为第 0 个路口。

输入(corner.in)

第 1 行两个整数 n,m (茫茫大街的长和宽) 
第 2 行到第 m+1 行,每行 n 个整数 Aij(第 i 行第 j 个地点的憧憬值)

对于 30%的数据, n,m<=50 
对于全部数据 n,m<=300

输出(corner.out)

一个整数 sum (可以得到的最大憧憬值)

样例

corner.in

4 4 
1 1 1 1 
1 1 0 1 
1 1 1 1 
1 1 1 1

corner.out

23

解答

本题可动态规划的思路求解,对任意点到起点进行23步到达起点的憧憬值进行求解,则有以下状态转移方程,

ans[i][j][23] = max(ans[i + oneStepChangeInI][j + oneStepChangeInJ][22] + value[i][j])

具体代码实现如下。

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

#define MAX 1000000000

FILE *in, *out;
int n, m;
int jie[302][302] = {0}, qidian[2] = {0};
int walk[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
double ans[302][302][25] = {0};
double maxnum = 0;

double fdosearch(int x, int y, int step) {
  if (ans[x][y][step])
    return (ans[x][y][step]);

  if (x == qidian[0] && y == qidian[1]) {
    if (step == 0) {
      return (1);
    } else {
      return (0);
    }
  }

  if (step == 0) {
    ans[x][y][0] = -1;
    return (-1);
  }

  double tem = -MAX;
  int i;
  for (i = 0; i < 4; i++)
    if (step > 0 && x + walk[i][0] > 0 && x + walk[i][0] <= m &&
        y + walk[i][1] > 0 && y + walk[i][1] <= n &&
        (jie[x + walk[i][0]][y + walk[i][1]] != -1)) {
      if (fdosearch(x + walk[i][0], y + walk[i][1], step - 1) > 0)
        if (tem < ans[x + walk[i][0]][y + walk[i][1]][step - 1] + jie[x][y])
          tem = ans[x + walk[i][0]][y + walk[i][1]][step - 1] + jie[x][y];
    }
  if (tem != -MAX) {
    ans[x][y][step] = tem;
    return (1);
  } else {
    ans[x][y][step] = -1;
    return (-1);
  }
}

int main() {
  in = fopen("corner.in", "r");
  out = fopen("corner.out", "w");

  fscanf(in, "%d%d", &n, &m);
  int i, j;
  for (i = 1; i <= m; i++)
    for (j = 1; j <= n; j++) {
      fscanf(in, "%d", &jie[i][j]);
      if (jie[i][j] == 0) {
        qidian[0] = i;
        qidian[1] = j;
      }
    }

  for (i = 1; i <= m; i++)
    for (j = 1; j <= n; j++)
      if (jie[i][j] > 0)
        fdosearch(i, j, 23);

  maxnum = -MAX;
  for (i = 1; i <= m; i++)
    for (j = 1; j <= n; j++)
      if (ans[i][j][23] > maxnum)
        maxnum = ans[i][j][23];

  // for (i = 1; i <= m; i++) {
  //   for (j = 1; j <= n; j++)
  //     printf("%14.0f", ans[i][j][23]);
  //   printf("\n");
  // }
  // getchar();

  fprintf(out, "%.0lf\n", maxnum);
  fclose(in);
  fclose(out);

  return 0;
}

后记

个人感觉这题我的解答可能存在性能问题,不过因为没有测试数,所以以上解答仅为一种解答参考吧。另外,题目中的在23个路口上线左右拐弯,可能需要理解为经过23个路口。

参考


* cached version, generated at 2018-12-02 18:19:11 UTC.

Subscribe by RSS