首页 > 试题广场 >

走格子游戏

[编程题]走格子游戏
  • 热度指数:2359 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 10240M,其他语言20480M
  • 算法知识视频讲解
G社正在开发一个新的战棋类游戏,在这个游戏中,角色只能向2个方向移动:右、下。移动需要消耗行动力,游戏地图上划分M*N个格子,当角色移动到某个格子上时,行动力就会加上格子上的值K(-100~100),当行动力<=0时游戏失败,请问要从地图左上角移动到地图右下角至少需要多少起始行动力,注意(玩家初始化到起始的左上角格子时也需要消耗行动力)

输入描述:
第一行输入格子行列数(格式为 M N),第2~M+1行每行输入N个数,作为格子值K,中间以空格分割;0 < M, N < 1000,-100 < K < 100


输出描述:
初始最小行动力
示例1

输入

2 3
-2 -3 3
-5 -10 1

输出

6
#写一个python版的答案

#读取数据
m,n = map(int,input().split())
array = []
for _ in range(m):
    list1 = list(map(int,input().split()))
    array.append(list1)
#构建一个辅助数组,记录移动方向
#1表示竖直移动,0表示水平移动
line = [[0]*n for _ in range(m)]
for j in range(n-1):
    array[0][j+1] += array[0][j]
for i in range(m-1):
    array[i+1][0] += array[i][0]
#动态规划算每个点最小的体力值
for i in range(1,m):
    for j in range(1,n):
        if(array[i-1][j] > array[i][j-1]):
            array[i][j] += array[i-1][j]
            line[i][j] = 1
        else:
            array[i][j] += array[i][j-1]
#print(array)
#从右下角 往 左上角 回溯。 求得最小值
list1 = []
i = m-1
j = n-1
while(i>0 and j>0):
    if(line[i][j] == 1):
        i -= 1
    else:
        j -= 1
    list1.append(array[i][j])
if(i>0):
    for k in range( i):
        list1.append(array[k][0])
else:
    for k in range( j):
        list1.append(array[0][k])
#print(list1)
res = min(list1)
print(max(-res+1,1))

发表于 2019-04-21 16:00:08 回复(1)

/ 本题dp可解毫无疑问;本人较懒就用了二分答案+dfs判断的方式。从题意易知起始的大小与路径中最小值最大的情况成正比,故而枚举答案,复杂度O(logn),对于每次枚举判断是否可行,即路径中存在一条路恒>0,复杂度O(n).这样一来综合复杂度O(nlogn),n=1e6,故而可解。 /

include <iostream>

include <cstring>

include <string>

int b[1001][1001],a[1001][1001],c[1001][1001],n,m;
void dfs(int x,int y)
{
if(x>n||y>m||a[x][y]<=0||c[x][y])return;
c[x][y]=1;
dfs(x+1,y);
dfs(x,y+1);
}
int main()
{
std::cin>>n>>m;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)std::cin>>b[i][j];

int l=1,r=1e9,mid,g=1e9;

while(l<=r)
{
    int mid=(l+r)/2;
    std::memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=b[i][j];
    a[1][1]+=mid;

    for(int i=2;i<=m;i++)a[1][i]+=a[1][i-1];
    for(int j=2;j<=n;j++)a[j][1]+=a[j-1][1];

    for(int i=2;i<=n;i++)
        for(int j=2;j<=m;j++)a[i][j]+=std::max(a[i-1][j],a[i][j-1]);
    dfs(1,1);
    if(c[n][m])
    {
        g=std::min(g,mid);
        r=mid-1;
    }
    else l=mid+1;
}
std::cout<<g<<std::endl;

}

编辑于 2018-09-03 17:45:39 回复(0)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        int[][] vals = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                vals[i][j] = in.nextInt();
            }
        }
        int[][] dp = new int[m+1][n+1];
        for (int i = m-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                dp[i][j] = Math.min(Math.max(1, dp[i+1][j]), Math.max(1, dp[i][j+1])) - vals[i][j];
            }
        }
        dp[0][0] = dp[0][0] > 0 ? dp[0][0] : 1;
        System.out.println(dp[0][0]);
    }
}

发表于 2018-09-03 16:56:17 回复(2)
/*
网上有用动态规划,但是觉得太绕了。提起迷宫,果然还是第一个想起回溯法。
解题思路大概是 剪枝回溯,在每个路线中,保存历史上最高的体力消耗,然后选出每个路线中体力消耗中最少的路线。
*/

// From me回溯法 
#include<iostream>
using namespace std;
int temp=-10000;
int m,n;
void Finish(int map[1000][1000],int i,int j,int flag,int num)
{
    if( i == m-1 && j== n-1)
    {
        if(flag > temp)
        {
            temp =flag;
        }
        return;
    }
     
    int k=0;
    int a=flag;
    if(temp<flag)
{
    
    if(i+1<m )
    {
        k= num+map[i+1][j];
        if(k < a)
        {
            a=k;
        }
        Finish(map,i+1,j,a,k);
    }
    if(j+1<n)
    {
        a=flag;
        k= num+map[i][j+1];
        if(k < a)
        {
            a=k;
        }
        Finish(map,i,j+1,a,k);
    }
}
}
 
int main()
{
    while(cin>>m>>n)
    {
        int map[1000][1000];
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                cin>>map[i][j];
            }
        }
        Finish(map,0,0,map[0][0],map[0][0]);
        int res;
        if(temp <0)
        {
            res=abs(temp)+1;
             cout<<res;
        }
        else 
        {
            cout<<1;
        }

         
    }
}

 
发表于 2018-07-09 11:39:15 回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        int m = Integer.parseInt(strs[0]), n = Integer.parseInt(strs[1]);
        int[][] grid = new int[m][n];
        for (int i = 0; i < m; i++) {
            strs = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                grid[i][j] = Integer.parseInt(strs[j]);
            }
        }

        int[][] dp = new int[m + 1][n + 1];
        dp[m][n] = 1;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - grid[i][j]);
            }
        }
        System.out.println(dp[0][0]);
    }
}

发表于 2019-02-02 13:22:25 回复(1)

【关键点】角色的三种状态:

  1. 角色在(i, j)之前(即在(i-1, j)或者(i, j-1),下一步即将移动到(i, j))行动力用dp[i][j]表示,比如初始行动力为dp[0][0],下一步即将移动到(0, 0)

  2. 角色在(i, j)(下一步即将移动到(i+1, j)或者(i, j+1))行动力等于dp[i][j]+a[i][j],比如初始行动力为dp[0][0],角色在(0, 0)时行动力为dp[0][0]+a[0][0]

  3. 角色在(i, j)之后(即在(i+1, j)或者(i, j+1),上一步在(i, j)),此时有min(dp[i+1][j], dp[i][j+1])等于dp[i][j]+a[i][j]

【分析】dp[i][j]表示角色尚在格子(i, j)之前并且即将要移动到格子(i, j)时的行动力。

dp[0][0]表示初始的行动力。

当行动力小于或者等于0时游戏失败,dp[i][j]必然大于或者等于(对应递推公式的max)1,即dp[i][j]>=1

dp[i][j]+a[i][j]表示角色在格子(i, j)但尚未往下移动时的行动力,此时行动力为min(dp[i+1][j], dp[i][j+1])采用min是因为最后要求的是最小值。

最后求解初始时刻的行动力,则应该从后往前推理,可得,

dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) – a[i][j])
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int m,n;
    cin>>m>>n;
    vector<vector<int> > a(m,vector<int>(n,0));
    vector<vector<int> > dp(m+1,vector<int>(n+1,0));
    for(int i=0;i<m;++i)
        for(int j=0;j<n;++j)
            cin>>a[i][j];
    for(int i=m-1;i>=0;--i)
        for(int j=n-1;j>=0;--j)
            dp[i][j]=max(1,min(dp[i+1][j],dp[i][j+1])-a[i][j]);
    cout<<dp[0][0]<<endl;
    return 0;
}

编辑于 2020-03-20 02:15:55 回复(5)
说说排行榜的题解是错误的:
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <sstream>
#include <stdlib.h>
#include <algorithm>
#include <limits.h>

#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define ll long long

using namespace std;

int main() {
    int m, n;
    scanf("%d%d", &m, &n);
    vector<vector<int>> nums(m + 1, vector<int>(n + 1, 0)), v(m + 1,
                     vector<int>(n + 1, 0)), dp(m + 1, vector<int>(n + 1, 1));

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &nums[i][j]);

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            if (i == 1 || j == 1) {
                if (i == 1) {
                    dp[i][j] = max(dp[i][j - 1], -(v[i][j - 1] + nums[i][j]) + 1);
                    v[i][j] = v[i][j - 1] + nums[i][j];
                } else {
                    dp[i][j] = max(dp[i - 1][j], -(v[i - 1][j] + nums[i][j]) + 1);
                    v[i][j] = v[i - 1][j] + nums[i][j];
                }
            } else {
                dp[i][j] = min(max(dp[i][j - 1], -(v[i][j - 1] + nums[i][j]) + 1),
                               max(dp[i - 1][j], -(v[i - 1][j] + nums[i][j]) + 1));
                v[i][j] = max(v[i][j - 1] + nums[i][j], v[i - 1][j] + nums[i][j]);
            }
            //cout << i << " " << j << " " << dp[i][j] << endl;
        }

    printf("%d\n", dp[m][n]);
    return 0;
}
提供两组不能通过的测试用例:
3 3
0 -2 3
-1 0 0
-3 -3 -2

2 4
1 -4 5 -99
2 -2 -2 -1

发表于 2023-09-22 02:15:45 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] arr = new int[n][m];
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    arr[i][j]=sc.nextInt();
                }
            }
            int[][] dp = new int[n][m];
            dp[n-1][m-1]=1;
            for(int i=n-2;i>=0;i--){
                dp[i][m-1]=Math.max(1,dp[i+1][m-1]-arr[i][m-1]);
            }
            for(int i=m-2;i>=0;i--){
                dp[n-1][i]=Math.max(1,dp[n-1][i+1]-arr[n-1][i]);
            }
            for(int i=n-2;i>=0;i--){
                for(int j=m-2;j>=0;j--){
                    dp[i][j]=Math.max(1,Math.min(dp[i+1][j],dp[i][j+1])-arr[i][j]);
                }
            }
            System.out.println(dp[0][0]);
        }
    }
}
思路就是动态规划,不过是从右下角倒着往前更新dp数组,计算到达每个格子之前,需要的最小行动力,保证到达每个格子之前行动力都至少为1.
发表于 2020-09-21 10:12:46 回复(0)
#include<iostream>
using namespace std;
const int N = 1010, M = 1010;
int a[N][M], dp[N][M];
int n,m;
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            cin >> a[i][j];
    
    
    for(int i = n - 1; i >= 0; --i)
        for(int j = m - 1; j >= 0; --j)
            dp[i][j]= min(max(1,dp[i+1][j]-a[i][j]),max(dp[i][j+1]-a[i][j],1));
    
    cout << dp[0][0] << endl;
    
    return 0;
}

编辑于 2020-04-28 10:07:10 回复(0)
import sys
class Solution(object):
    def solveGrid(self,grid):
        self.M = len(grid) - 1  
        self.N = len(grid[0]) - 1
        self.dp = [[sys.maxint for j in range(self.N+1)] for i in range(self.M+1)]
        self.countPaths(grid, 1, 1, 1, [])
        return self.dp[self.M][self.N]

    def countPaths(self, grid, row, col, level, path):
        if path:
            path.append(path[-1] + grid[row][col])
        else:
            path.append(grid[row][col])
            
        tmp = max(1, -min(path) + 1)
        self.dp[row][col] = min(self.dp[row][col], tmp) 
        
        if row == self.M and col == self.N:
            return
        
        if col+1<=self.N \
        and tmp == self.dp[row][col] \
        and self.dp[row][col] < self.dp[row][col+1] \
        and self.dp[row][col] < self.dp[self.M][self.N]:
            self.countPaths(grid,row,col+1, level+1, path)
            path.pop()        
        
        if  row+1<=self.M \
        and tmp == self.dp[row][col] \
        and self.dp[row][col] < self.dp[row+1][col] \
        and self.dp[row][col] < self.dp[self.M][self.N]:
            self.countPaths(grid,row+1,col, level+1, path)
            path.pop()

if __name__ == "__main__":
    line = raw_input()
    lines = line.split()
    M, N = int(lines[0]), int(lines[1])
    grid = []
    grid.append([0 for j in range(N+1)])
    for _ in xrange(M):
        line = raw_input()
        lines = line.split()
        tmp = [0] + [int(item) for item in lines]
        grid.append(tmp)
    s = Solution()
    print s.solveGrid(grid)
递归 加 剪枝 即可求解
发表于 2019-05-26 20:00:57 回复(0)
A到吐血
#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
int n,m;
int grid[1000][1000];
int ans;
void dfs(int x,int y,int temp,int w) {
    if (x<0||x>=m||y<0||y>=n) {
        return ;
    }
    if (y==n-1&&x==m-1) {
        temp=min(temp,w+grid[y][x]+temp);
        ans=max(temp,ans);
        return ;
    } else if (temp>ans) {
        int res1=w+grid[y][x];
        int res=temp;
        if (res1<=0) {
            res+=res1;
            res1=0;
        }
        //int res=min(temp,res1);
        dfs(x+1,y,res,res1);
        dfs(x,y+1,res,res1);
    }
}

int main() {
    while (cin>>n>>m) {
        for (int i=0;i<n;i++) {
            for (int j=0;j<m;j++) {
                scanf("%d",&grid[i][j]);
            }
        }
        ans=-100000000;
        int temp=grid[0][0];
        dfs(0,0,0,0);
        //dfs(0,0,0,temp);
        cout<<abs(ans)+1<<endl;
    }
    return 0;
}

发表于 2019-02-08 15:57:16 回复(0)
采用动态规划的思路完成:
[M,N] = [int(i) for i in raw_input().split()]
K = []
for i in range(M):
    temp = [int(i) for i in raw_input().split()]
    K.append(temp)
dp = [-100001]*(N*M)
dp2 = [-100001]*(N*M)
dp[0] = K[0][0]
dp2[0]= K[0][0]
for j in range(1,N):
    dp[j] = K[0][j] + dp[j-1]
    dp2[j] = min(dp[0:j+1])
for i in range(1,M):
    dp[i*N] = K[i][0] + dp[(i-1)*N]
    dp2[i*N] = min(dp2[(i-1)*N], dp[i*N])
for i in range(1,M):
    for j in range(1,N):
        if min(dp[(i-1)*N+j], dp[i*N+j-1])+K[i][j] >=\
            max(dp2[(i-1)*N+j], dp2[i*N+j-1]):
            if dp2[(i-1)*N+j]> dp2[i*N+j-1]:
                dp[i*N+j] = dp[(i-1)*N+j] + K[i][j]
                dp2[i*N+j] = dp2[(i-1)*N+j]
            else:
                dp[i*N+j] = dp[i*N+j-1] + K[i][j]
                dp2[i*N+j] = dp2[i*N+j-1]
        elif max(dp[(i-1)*N+j], dp[i*N+j-1])+K[i][j] <=\
            max(dp2[(i-1)*N+j], dp2[i*N+j-1]):
            dp[i*N+j] = max(dp[(i-1)*N+j], dp[i*N+j-1]) + K[i][j]
            dp2[i*N+j] = dp[i*N+j]
        else:
            dp[i*N+j] = max(dp[(i-1)*N+j], dp[i*N+j-1]) + K[i][j]
            if dp[(i-1)*N+j]> dp[i*N+j-1]:
                dp2[i*N+j] = dp2[(i-1)*N+j]
            else:
                dp2[i*N+j] = dp2[i*N+j-1]
'''
print K
print dp
print dp2
'''
if dp2[-1]>0:
    print 1
else:
    print 1-dp2[-1]
 
发表于 2018-08-24 02:51:10 回复(0)
经典2维dp

import sys
lines = []
try: 
    while True:
        line = sys.stdin.readline().strip()
        if line == '':
            break 
        lines.append(line)
except: 
    pass

n = int(lines[0].split()[0])
m = int(lines[0].split()[1])
A=[[] for i in range(n)]
save = [[None for j in range(m)] for i in range(n)]
for i in range(n):
    for j in lines[i+1].split():
        A[i].append(int(j))
        
        
def dfs(A,save,i,j):
    if i>n or j>m or i<0 or j<0:
        return -100000,10000
    if save[i][j] is not None:
        return save[i][j][0],save[i][j][1]
    if i==0 and j==0:
        left,leftmax,upper,uppermax = 0,0,0,0
    else:
        left,leftmax = dfs(A,save,i,j-1)
        upper,uppermax = dfs(A,save,i-1,j)
    lcur = A[i][j]+left
    lmax = leftmax
    if lcur < leftmax:
        lmax = lcur
    ucur = A[i][j]+upper
    umax = uppermax
    if ucur < uppermax:
        umax = ucur
        
    if umax > lmax:
        save[i][j] = (ucur,umax)
        return ucur,umax
    else:
        save[i][j] = (lcur,lmax)
        return lcur,lmax

ms,ma = dfs(A,save,n-1,m-1)
if ma<0:
    print -ma+1
else:
    print 1

发表于 2018-08-15 21:26:20 回复(0)