jzoj 1579. 【普及模拟】老鼠

发布于 2019-03-21  795 次阅读


 

题目描述

   最近小h家闹鼠灾,弄得小h十分恼火。为了解决老鼠的问题,小h根据老鼠的特点想出了一个方法。假设小h 的家是一个n*n的格子,每个格子都有一定的食物,数量在0到100之间,经过观察,老鼠的窝在(1,1)的位置,老鼠吃东西有个特点,到哪个地方,就把这个地方的食物都吃掉,而且每次都比上一次吃的食物要多,因此它们总会有个停止的地方,而且,这些老鼠一次最多可以跳k格,不过只能按x轴或y轴方向来跳。现在,小h给出食物的分布,他想知道一只老鼠最多可以吃到多少食物。

 

输入

第一行,n,(1<=n<=100),k,(0<=k<=n),表示n*n的格子,老鼠一次最多跳k格。

   接下来的n行,每行n个数,表示这个方格上的食物数量。

输出

一个数,表示一只老鼠最多可以吃到的食物。

 

一道搜索题,搜索每一个点可以到达的位置,如果当前的数比这个点的数要大就不用搜索这一个点,不然会超时

const
  b:array[1..4,1..2] of integer=((1,0),(-1,0),(0,1),(0,-1));
var
  a,f:array[-100..1000,-100..1000] of longint;
  i,j,k,n,m,s,max,x,y:longint;
procedure dfs(x,y:longint);
var
  i,j:longint;
begin
  for i:=1 to 4 do
    begin
     for j:=1 to k do
      if (a[x,y]0) and (y+j*b[i,2]>0) and (x+j*b[i,1]<=n) and (y+j*b[i,2]<=n) then
        begin
          if f[x+j*b[i,1],y+j*b[i,2]]

 

]]>