# 11253: 【原1253】圣盔谷之战

### 题目描述

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

## Description

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

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

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

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

（圣盔谷可以视为第0行）

## 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;
}
``````