比赛(Test):查看题目 Show Problem

赛题题目:走卒

所属比赛:第3次期中风波模拟赛

问题编号:362 [提交该赛题]

描述: 【问题背景】

空闲之时，下局棋，未尝不好……

【问题描述】

一场恶战，浪子最后只剩下了一个卒。而对方，还有……这场战斗以失败告终。不过浪子突发其想，把一个卒放在一张N*M的棋盘上。每个格子都有个分值。卒每移动到一个格子，就要减少那个格子上的分值（先减再走）。假设卒刚开始只有T分，求出卒从左上角走到右下角所剩的最大分值。（为了简化问题，卒只能向左右或向下移动，最左端与最右端是不相连的。即卒在最某行最左端时，只能向右或向下移动；卒在最某行最右端时，只能向左或向下移动。）

当此时，某位同学把浪子喊去开唰（就是拿很多题目来……），浪子只好发到网上来求助。

输入格式: 第1行，三个数：N，M，T（1≤N，M≤100，1≤T≤1000）。

接下来N行，每行M个数。第I行的第J个数A[I，J]表示这格的分值（0≤A[I，J]≤10）

输出格式: 若卒走到右下角时，所剩的最大分值为正，那么输出所剩的最大分值。反之，则输出“DONOT HAVE MORE”（不包括引号）

输入文件: 直接输入即可

输出文件: 直接输出即可 注意,不要在最后输出空行或空格!

样例输入: 3 3 100

7 8 9

4 5 6

1 2 3

样例输出: 83

【样例说明】

从左上角到右下脚的最佳方案为：下、下、左、左。所剩分值为100-7-4-1-2-3=83

*/

#define INIDENTIFY -10000

#include<iostream>

using namespace std；

int n,m,t；

int dp[101][101],mark[101][101]；

bool visited[101][101]；

/*int*/void dfs_try(int x,int y,int have){

if (x<1||x>n||y<1||y>m||visited[x][y]) return /*INIDENTIFY*/；

if (dp[x][y]!=INIDENTIFY){

if (dp[x][y]<have-mark[x][y])

dp[x][y]=have-mark[x][y]；

return /*dp[x][y]*/；

}

if (have<=mark[x][y])

return /*dp[x][y]*/；

visited[x][y]=true；

dp[x][y]=have-mark[x][y]；

dfs_try(x-1,y,dp[x][y])；

dfs_try(x+1,y,dp[x][y])；

dfs_try(x,y+1,dp[x][y])；

visited[x][y]=false；

}

int main (void){

cin>>n>>m>>t；

for (int i=1；i<=n；++i)

for (int j=1；j<=m；++j){

cin>>mark[i][j]；

visited[i][j]=false；

dp[i][j]=INIDENTIFY；

}

dfs_try(1,1,t)；

if (dp[n][m]==INIDENTIFY)

cout<<"DONOT HAVE MORE"；

else cout<<dp[n][m]；

// while (1)；

return 0；

}