GFOJ Problem1513 :老鼠题解

Туполев · 2018-07-16 20:11:37 · 个人记录

原题

题目描述

最近小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个数，表示这个方格上的食物数量。

输出格式：

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

题解

首先审清题目，知道一个大概题意。~~应该可以看出是深搜的题吧~~

然后开始写代码吧......

思路（这次脑洞较大）：

先将所有格子转化成一维数组，然后按米粒数从小到大排序。因为我们从（1,1）开始走，所以将（1,1）赋值为有答案，答案为（1,1）的米粒数。然后从米粒的大小扫，如果在当前米粒数的那行或那列有小于此格米粒数的格子，且当个已被赋值成有值（初始化的时候只有（1,1）赋值成有值，所以可以确保从（1,1）往后生成），则当前格子的总值就是那个格子的值加上本格子的米粒数。当然for一行一列，要取一个叫max。最后for一遍整张图的值，取max，既是答案。

注意事项：

看清样例，分析好题目和样例
避开TLE！！！
注意图论算法的实现过程

其他详见标程注释

标程

#include<bits/stdc++.h>//老鼠 
using namespace std;
int j,k,n,m,tot,ans,top,f[105][105],r[105][105];
struct abc{
int x,y,num,tot;
}a[10005];
int cmp(abc a,abc b){//结构体比较函数 
if(a.num<b.num) return 1;
else return 0;
}
int read(){//读入函数 ，此写法可以加速读入，防止TLE 
char c;
int x;
while(c=getchar(),c<'0'||c>'9');
x=c-'0';
while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';
return x;
}
int main(){
n=read();k=read();
int i,j;
for(i=1;i<=n;i++)for(j=1;j<=n;j++){//将格子转化成一维数组 
    f[i][j]=read();
    a[++top].x=i;
    a[top].y=j;
    a[top].num=f[i][j];
 } 
sort(a+1,a+1+top,cmp);//排序 
r[1][1]=f[1][1];//将（1,1）赋值为有答案，答案为（1,1）的米粒数
for(i=1;i<=top;i++){// 从米粒的大小扫
    if(a[i].num==f[1][1]) continue;
    for(j=max(a[i].x-k,1);j<=min(a[i].x+k,n);j++) if(f[j][a[i].y]<a[i].num) a[i].tot=max(a[i].tot,a[i].num+r[j][a[i].y]);
    for(j=max(a[i].y-k,1);j<=min(a[i].y+k,n);j++) if(f[a[i].x][j]<a[i].num) a[i].tot=max(a[i].tot,a[i].num+r[a[i].x][j]);
    if(a[i].tot!=a[i].num) r[a[i].x][a[i].y]=a[i].tot;//此处详见思路 
}
for(i=1;i<=n;i++)  for(j=1;j<=n;j++) ans=max(ans,r[i][j]);//把图遍历一遍，max求答案 
if(ans==0) ans=f[1][1];
cout<<ans;//输出答案 
return 0;
}

GFOJ Problem1513 :老鼠 题解

原题