汽车加油问题

[效云 李]

给定一个N*N 的方形网格，设其左上角为起点◎，坐标为（1，1），X轴向右为正，Y 轴向下为正，每个方格边长为1。一辆汽车从起点◎出发驶向右下
角终点▲，其坐标为（N， N）。在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则：（1）汽车只能沿网格
边行驶，装满油后能行驶K 条网格边。出发时汽车已装满油，在起点与终点处不设油库。（2）当汽车行驶经过一条网格边时，若其X 坐标或Y 坐标减小，
则应付费用B，否则免付费用。（3）汽车在行驶过程中遇油库则应加满油并付加油费用A。（4）在需要时可在网格点处增设油库，并付增设油库费用 C（不
含加油费用A）。（5）(1)～(4)中的各数N、K、A、B、C均为正整数。

Input
输入的第一行是N，K，A，B，C的值，2 ≤ N ≤ 100， 2 ≤ K ≤ 10。第二行起是一个N*N 的0-1方阵，每行N 个值，至
N+1行结束。方阵的第i 行第j 列处的值为1 表示在网格交叉点（i，j）处设置了一个油库，为0 时表示未设油库。各行相邻的2 个数以空格分
隔。

Output
程序运行结束时，将找到的最优行驶路线所需的费用，即最小费用输出

Sample Input
9 3 2 3 6
0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 1 0 0
1 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0
0 1 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1
1 0 0 1 0 0 0 1 0
0 1 0 0 0 0 0 0 0

Sample Output
12

[效云 李]

一开始想，没想出来，后来看了答案提示，说用备忘录法结合动态规划，来解决。但在备忘录法时，每一个点的值依赖于周围4个方向的值，那这样做必然导致死
循环，我不知道这个问题怎么解决，这个问题如何用动态规划解决？
望大家指教

[higer]

别担心，我正在做这道题。

[孔令军]

嘎嘎 牛X 哈哈 加油

 

 

2009-04-15

---

孔令军

---

发件人： higer

发送时间： 2009-04-15  16:24:02

收件人： 编程爱好者天地

抄送：

主题： Re: 汽车加油问题

[孔令军]

我一个不会 看着头就大啊 哈哈

 

 

2009-04-15

---

孔令军

---

发件人： higer

发送时间： 2009-04-15  16:24:02

收件人： 编程爱好者天地

抄送：

主题： Re: 汽车加油问题

[zhong nanhai]

你没深入去想。。。
不过我现在也是一点头绪都冇得。。。

On 4/15/09, 孔令军 <allenk...@gmail.com> wrote:
> 我一个不会 看着头就大啊 哈哈
>
>
> 2009-04-15
>
>
>
> 孔令军

[朱涛]

你们还真爽，有哗哗的时间学习算法，我们还在实验室里搞无聊的项目，5555
等着吸收你们的精华部分了。

--

朱涛
中科院软件所基础软件国家工程中心
http://twitter.com/towerjoo

2009/4/15 zhong nanhai <higerin...@gmail.com>:

[zhong nanhai]

有项目做就可以，不像我们没项目做，天天搞一些扯淡的东西。所以，对于我们而言还是搞搞算法比较有意义。

[王海龙]

我也搞算法,为什么就没有时间搞呀.可见整天在忙着搞扯淡的事情了.

[higer]

我下午想了想，死循环可以通过设置一个最佳路径就可以控制了，可以参考严蔚敏的课本P51的迷宫问题。
但是，我依然不知道该如何计算每一个点，也就是如何计算这个子问题。
当计算一个点的时候，它周围4个点都是未知的，有怎么样的一个循环计算的步骤实在是不清楚，即使偶尔做些假设，但是依然没有十分的把握证明自己的假设是
正确的。

On Apr 15, 4:19 pm, 效云 李 <lixiaoyun...@gmail.com> wrote:

[李效云]

你把程序给写出来，看看，我觉的。。。。

2009/4/21 higer <higerin...@gmail.com>

[zhong nanhai]

你没看我的问题吗？
我现在不知道怎么计算各个子问题，程序没法写，刚才找你你都不在座位上。

[higer]

这个题搞了好长时间，死活还是搞不出来。
发现它原来跟"迷宫问题"差别很大的，对于迷宫问题，总可以由起始点一步一步往下计算，找到一个最优点，如果不是最优，可以回溯。但是对于这个"汽车加
油"问题，一个点最优值的计算，不是简单的从起始点进行的，它的最优值还可能来自于它后面的点，也就是说我们并不能由一个点走到底，各点之间相互依赖，
并没有一个合适的位置导致循环或递归的结束。

[李效云]

对啊，这怎么解决啊，即使用DIJ算法，求最短路径也会有问题的，怎么办啊

2009/4/21 higer <higerin...@gmail.com>

[苏峰]

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX 10000000
#define  Num 50+1
using namespace std;

int memo[Num][Num];
bool oil[Num][Num];

int K,N;
int A,B,C;
static int len;//len is static

int S[4][3]={{-1,0,0},{0,-1,0},{1,0,B},{0,1,B}};

void init()
{
    scanf("%d",&N);scanf("%d",&K);scanf("%d",&A);
    scanf("%d",&B);scanf("%d",&C);
    len=K;
    //memset(oil,false,sizeof(oil));
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            int tmp;
            scanf("%d",&tmp);
            oil[i][j]=(tmp==1)?true:false;
        }
    }
   
    for(int i=0;i<Num;i++)
    {
        for(int j=0;j<Num;j++)
        {
            memo[i][j]=MAX;
        }
    }
    memo[1][1]=0;
}

int process(int x,int y)
{
    //the (x,y) was invalid
    if(x<1||y<1||x>N||y>N)
    {
        return MAX;
    }
    //x,y 有记录
    if(memo[x][y]<MAX)
    {
        if(oil[x][y]){
            memo[x][y]+=A;
            len=K;
        }
        else if(!oil[x][y] && len==0 && memo[x][y]<MAX){
            memo[x][y]+=(A+C);
            len=K;
        }
        len--;
        return memo[x][y];
    }

    if(x==1&&y==1)
    {
        return f[1][1];
    }

    /**
     *  not find in memo[x][y]
     */
    else{
        //int temp;
        for(int i=0;i<4;++i)
        {
            int temp=process(x+S[i][0],y+S[i][1])+S[i][2];
            if(memo[x][y]>temp)
            {
                memo[x][y]=temp;
            }
        }
        if(oil[x][y] && memo[x][y]<MAX)
        {
            memo[x][y] +=A;
            len=K;
        }
        else if(!oil[x][y] && len==0 && memo[x][y]<MAX)
        {
            memo[x][y]+=(A+C);
            len=K;
        }
       
        return memo[x][y];
    }
}

int main()
{
    init();
    int res=process(N,N);
    cout<<res<<endl;
}
代码有点乱，基本大致就是这个思路了，memo[N][N]作为memo数组记录。

2009/4/21 李效云 <lixiao...@gmail.com>

[higer]

我看了一些苏峰的程序，的确写的不错，跟标准答案非常接近，特别是int S[4][3]={{-1,0,0},{0,-1,0},{1,0,B},
{0,1,B}}; 用的很妙，给代码简化了很多（书上就是这么给出的）。我发现我们的程序之所以会出现死循环，与苏峰的程序最大的区别在于：//
x,y 有记录
if(memo[x][y]<MAX) ，他在一个点是否计算过这个地方加了判断，也就是说如果一个点的值不是Max，那么它一定计算过的，而
且这个计算的值也就一定是最优值。这样下来的话，程序到最后一定会计算在(1,1)这个位置，由于这个位置值存在，为0，程序会层层往回计算，从而所有
的点被计算到。
我们的误区（我跟李效云）在于：每次计算时把所有的点的计算方法都由周围4个点来计算，这样必然导致没有一个值是有效的值，相互依赖，最后导致死循环。
其实可以这样想，相互依赖最后会构成一个环，这环中当然包括(1,1)这个点，由于(1,1)这个位置最优值已知，所以环最后会在(1,1)断开，从而
解除了死循环。

> 2009/4/21 李效云 <lixiaoyun...@gmail.com>

>
> > 对啊，这怎么解决啊，即使用DIJ算法，求最短路径也会有问题的，怎么办啊
>

> > 2009/4/21 higer <higerinbeij...@gmail.com>

[李效云]

从今天晚上讨论的结果来看，我觉的，这个问题还是没解决

2009/4/22 higer <higerin...@gmail.com>

[zhong nanhai]

程序上能说通，
对于你的问题缺少一个证明。