Mouse

Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1059 Accepted Submission(s): 308

Problem Description

A greedy mouse cici ate rat poison by mistake. To save herself, she have to drink.

Cici can only walk in four ways that marked in the photoes followed and only move in the region that colored blue..She expend energy every step.There are cheese in every position which cici can eat to gain energy once she is there.He will never reach the river if she run out of energy.The initially energy of cici is energy of the cheese at the coordinate (0,0).
if when the mouse arrive a position has 0 energy , he can't eat the cheese.
Now can you help the wretched monse to calculate whether can he get to the river.
If she can,calculate the minimun energy of the maximal energy of every possible position of the river(Y = N-1).

Input

There are several test cases.In each case,there are three integers n(0<n<=200),m(0<m<=10),and k(0<k<=10)in the first line ,the next n lines followed. The second line has only one integer c(0<c<=100),the i-th line has m integers more than (i-1)th line.
k is the energy each step cost.

Output

If the monkey can not get to the river,print "what a pity mouse!!" int one line;If she can,calculate the minimun energy of the maximal energy of every possible position of the river(Y = N-1).

Sample Input

7 2 3
5
3 6 4
6 9 2 5 6
2 5 3 7 1 6 7
8 9 3 2 6 3 8 9 5
3 5 3 6 4 3 5 6 8 4 2
2 6 3 3 6 7 8 5 3 1 4 5 6

Sample Output

鼠标

问题描述

一只贪婪的老鼠误食了老鼠药。为了救自己，她必须喝酒。

茜茜只能以照片上标记的四种方式行走，并且只能在蓝色区域行走。她每走一步都消耗能量。每个部位都有奶酪，茜茜一到那里就可以吃奶酪来补充能量。如果她没力气了，他永远也到不了河边。cici的初始能量是奶酪在坐标(0,0)处的能量。

如果当老鼠到达一个位置时能量为0，他就不能吃奶酪了。

现在你能帮那个可怜的蒙斯算算他能不能到河边去。

如果她可以，计算河流的每个可能位置的最大能量的最小能量(Y = N-1)。

输入

有几个测试用例。在每种情况下，第一行有三个整数n(0第二行只有一个整数c(0

K是每一步所需的能量。

输出

如果猴子到不了河，就用一行写“真可惜老鼠!!”;如果猴子到不了河，就用一行写“真可惜老鼠!!”

样例输入

7 2 3

3 6 4

6 9 2 5 5

2 5 3 7 1 6 7

8 9 3 2 6 3 8 9 5

3 5 3 6 4 3 5 6 8 4 2

2 6 3 3 6 7 8 5 3 1 4 5 6

样例输出

题目大意：一只中毒的老鼠要到河边喝水解毒，开始老鼠在地图左上角（0，0），给它定义四个走向分别是向右一单位（0，1），向下一单位（1，0），向右下走日字（1，2）、（2，1）如图。地图共n行，第一行有一块地，每向下一行多m块地，最下面一行是河边。每块地上有一些奶酪，吃了能增长能量，原点的奶酪代表初始能量，每走一步会消耗k单位能量，如果消耗后所剩能量小于等于0，老鼠就死了（也没法吃这块地上的奶酪了）……问以最优策略抵达河边时最少有多少能量。

题目分析：数字三角形的变形。

代码：

#include<stdio.h>
#include<string.h>
int i,j,m,n,k,dp[210][2110],dir[4][2]={1,0,0,1,1,2,2,1};
int max(int a,int b,int c,int d)
{
    a=a>b?a:b;
    a=a>c?a:c;
    return a>d?a:d;
}
int judge(int x,int y)
{
    return x>=0&&y>=0&&dp[x][y]>0;
}
void f()
{
    int a[4],l,x,y,maxc;
    for(i=1;i<n;i++)
    {
        for(j=0;j<=m*i;j++)
        {
            for(l=0;l<4;l++)
            {
                x=i-dir[l][0];
                y=j-dir[l][1];
                a[l]=judge(x,y)?dp[x][y]-k:-1;
            }
            maxc=max(a[0],a[1],a[2],a[3]);
            dp[i][j]=maxc>0?dp[i][j]+maxc:-1;
        }
    }
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {
        memset(dp,-1,sizeof(dp));
        for(i=0;i<n;i++)
        {
            for(j=0;j<=m*i;j++)
            {
                scanf("%d",&dp[i][j]);
            }
        }
        f();
        for(j=-1,i=0;i<=m*(n-1);i++)
        {
            if(j<0)
                j=j>dp[n-1][i]?j:dp[n-1][i];
            else if(dp[n-1][i]>0)
                j=j<dp[n-1][i]?j:dp[n-1][i];
        }
        if(j==-1)
            printf("what a pity mouse!!\n");
        else 
            printf("%d\n",j);
    }
    return 0;
}

hdu 2118 Mouse

Mouse