首页 > 试题广场 >

精灵鼠从入口到出口的最少减少速度

[编程题]精灵鼠从入口到出口的最少减少速度

热度指数：3223 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

猛兽侠中精灵鼠在利剑飞船的追逐下逃到一个n*n的建筑群中，精灵鼠从（0,0）的位置进入建筑群，建筑群的出口位置为（n-1,n-1），建筑群的每个位置都有阻碍，每个位置上都会相当于给了精灵鼠一个固定值减速，因为精灵鼠正在逃命所以不能回头只能向前或者向下逃跑，现在问精灵鼠最少在减速多少的情况下逃出迷宫？

输入描述:

第一行迷宫的大小: n >=2 & n <= 10000；
第2到n+1行，每行输入为以','分割的该位置的减速,减速f >=1 & f < 10。

输出描述:

精灵鼠从入口到出口的最少减少速度？

示例1

输入

3
5,5,7
6,7,8
2,2,4

输出

算法知识视频讲解

勇敢牛牛，不怕困难！

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

int main(const int argc, const char* const argv[]) {
  int n;
  fscanf(stdin, "%d\n", &n);
  
  int x, y, grid[n][n];
  for (y = 0; y < n; ++y)
    for (x = 0; x < n; ++x)
      fscanf(stdin, "%d,", *(grid + y) + x);
  
  for (x = 1; x < n; ++x) grid[0][x] += grid[0][x - 1];
  for (y = 1; y < n; ++y) grid[y][0] += grid[y - 1][0];
  
  for (y = 1; y < n; ++y)
    for (x = 1; x < n; ++x)
      grid[y][x] += fmin(grid[y - 1][x], grid[y][x - 1]);
  
  fprintf(stdout, "%d\n", grid[n - 1][n - 1]);
  return 0;
}

发表于 2021-08-05 19:09:25 回复(0)