Skip to content

11253: 【原1253】圣盔谷之战

题目

题目描述

author: Kalethars 张晔 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1253

Description

洛汗正面临他们历史上最严峻的一场战役——圣盔谷之战。作为洛汗的军队统帅,伊欧墨要调遣军队来拯救洛汗国于存亡之际。在圣盔谷外的广袤平原上,散布着M×N个营地。每个营地驻扎着一些骑兵且每个营地的骑兵数量均不相同(如果有骑兵的话)。伊欧墨每次会去当前骑兵最多的营地去调遣军队,然后再去剩下营地中骑兵最多的一个调遣军队,以此类推。但是艾辛格的半兽人军队在K小时内就会抵达圣盔谷。所以他在K小时内必须要返回圣盔谷。

伊欧墨在每个小时内,可以做下列四件事情之一。

(1) 从圣盔谷赶到最近的营地(即第一行)。

(2) 从一个营地赶到与之前后左右相邻的另一个营地。

(3) 调遣一个营地的骑兵。

(4) 从最靠近圣盔谷的营地回到圣盔谷,并结束调遣军队的行动。

(圣盔谷可以视为第0行)

现在给定M×N个营地和其中骑兵驻扎的数量,伊欧墨想知道在艾辛格军队到达之前,他最多能调遣多少骑兵呢?

Input Format

输入文件的第一行包括三个整数,M, N和K,用空格隔开;表示平原的大小为M×N(1<=M,N<=20),艾辛格到达的时间为K(0<=K<=1000)小时。接下来的M行,每行包括N个非负整数,也用空格隔开;第i+1行的第j个整数Aij(0<=Aij<=500)表示营地(i, j)中驻扎的骑兵数量,0表示该营地中没有骑兵。

Output Format

输出文件包括一行,这一行只包含一个整数,即在K小时内,伊欧墨能调遣多少骑兵。

Sample Input 1

6 7 21
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0

Sample Output 1

37
(解释:圣盔谷->(1,2)->(2,2)->(3,2)->(4,2)->(4,2)调遣15->(3,2)->(2,2)->(2,3)->(2,4)->(2,5)->(2,5)调遣13->(2,4)->(3,4)->(4,4)->(5,4)->(5,4)调遣9->(4,4)->(3,4)->(2,4)->(1,4)->圣盔谷)

Sample Input 2

6 7 20
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0

Sample Output 2

28

WashSwang's solution

#include <iostream>
#include <cstdio>
int x[501],y[501],m,n,p,q,k,curx,cury,sum;
int main() {
    scanf("%d%d%d",&m,&n,&k);
    for (int i=1;i<=m;++i)
        for (int j=1;j<=n;++j)
        {
            scanf("%d",&p);
            x[p]=i;
            y[p]=j;
        }
    for (q=500;q>=1;--q)
        if (x[q]>0)
        {
            if (k-2*x[q]-1>=0)
            {
                k-=x[q]+1;
                sum+=q;
                curx=x[q];
                cury=y[q];
            }
            else
            {
                printf("%d",0);
                return 0;
            }
            break;
        }
    for (--q;q>=1;--q)
    {
        if (x[q]>0)
        {
            if (k-abs(curx-x[q])-abs(cury-y[q])-x[q]-1>=0)
            {
                k-=abs(curx-x[q])+abs(cury-y[q])+1;
                sum+=q;
                curx=x[q];
                cury=y[q];
            }
            else
            {
                printf("%d",sum);
                return 0;
            }
        }
    }
    printf("%d",sum);
    return 0;
}