关注
第一题动态规划解法,代码没优化,中间还有调试用的输出,额,有点长。大体思想,先求出(0,0)到各个点的最大剩余体力,然后从(0,m)开始倒推路径。
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int m = sc.nextInt();
int P = sc.nextInt();
int[][] nums = new int[n][m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
nums[i][j] = sc.nextInt();
}
}
if(n == 1){
System.out.println(P - m + 1);
}
if(m == 1){
System.out.println(P);
}
int[][] tili = new int[n][m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
tili[i][j] = -1;
}
}
getSolution(nums, tili, P);
dis(nums);
System.out.println("tili");
dis(tili);
findPath(nums, tili);
}
}
public static void getSolution(int[][] nums, int[][] tili ,int P){
int n = nums.length;
int m = nums[0].length;
tili[0][0] = P;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(nums[i][j] == 0){
continue;
}
update(nums, tili, i, j);
}
}
}
public static void update(int[][] nums, int[][] tili, int i, int j){
if(tili[i][j] <= 0){
return;
}
if(i>0){
if(nums[i-1][j] == 1){
int p = tili[i][j] - 3;
if(tili[i-1][j] < p){
tili[i-1][j] = p;
update(nums, tili, i-1, j);
}
}
}
if(i<nums.length-1){
if(nums[i+1][j] == 1){
int p = tili[i][j];
if(tili[i+1][j] < p){
tili[i+1][j] = p;
update(nums, tili, i+1, j);
}
}
}
if(j > 0){
if(nums[i][j-1] == 1){
int p = tili[i][j] - 1;
if(tili[i][j-1] < p){
tili[i][j-1] = p;
update(nums, tili, i, j-1);
}
}
}
if(j < nums[0].length-1)
{
if(nums[i][j+1] == 1){
int p = tili[i][j] - 1;
if(tili[i][j+1] < p){
tili[i][j+1] = p;
update(nums, tili, i, j+1);
}
}
}
}
public static void findPath(int[][] nums, int[][] tili){
int n = tili.length;
int m = tili[0].length;
if(tili[0][m-1] == -1){
System.out.println("Can not escape!");
}
Stack<String> stack = new Stack<String>();
String str = "[0," + (m-1) + "]";
stack.push(str);
findnext(tili, 0, m-1, stack);
while(!stack.isEmpty()){
System.out.print(stack.pop());
if(!stack.isEmpty()){
System.out.print(",");
}
}
}
public static void findnext(int[][] tili, int i, int j, Stack<String> s){
if(i==0 && j==0){
// String str = "[0,0]";
// s.push(str);
return;
}
int up=0, down=0, left=0, right=0;
int cur = tili[i][j];
if(i > 0){
up = tili[i-1][j];
if(up == cur){
String str = "[" + (i-1) + "," + j + "]";
s.push(str);
findnext(tili, i-1, j, s);
return;
}
}
if(i < tili.length-1){
down = tili[i+1][j];
if(cur == down - 3){
String str = "[" + (i+1) + "," + j + "]";
s.push(str);
findnext(tili, i+1, j, s);
return;
}
}
if(j >0){
left = tili[i][j-1];
if(cur == left - 1){
String str = "[" + (i) + "," + (j-1) + "]";
s.push(str);
findnext(tili, i, j-1, s);
return;
}
}
if(j < tili[0].length-1){
right = tili[i][j+1];
if(cur == right - 1){
String str = "[" + (i) + "," + (j+1) + "]";
s.push(str);
findnext(tili, i, j+1, s);
return;
}
}
}
public static void dis(int[][] nums){
for(int i=0; i<nums.length; i++){
System.out.println(Arrays.toString(nums[i]));
}
}
}
查看原帖
点赞 评论
相关推荐
05-14 15:17
青岛滨海学院 Java 点赞 评论 收藏
分享
07-03 14:11
广西大学 渠道销售 点赞 评论 收藏
分享
Java抽象小篮子:go批这招太狠了
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 计算机有哪些岗位值得去? #
9284次浏览 88人参与
# 电网笔面经互助 #
35947次浏览 348人参与
# 实习生的蛐蛐区 #
28294次浏览 216人参与
# 听劝,这个简历怎么改 #
177337次浏览 1150人参与
# 应届生,你找到工作了吗 #
15337次浏览 127人参与
# 你找工作的时候用AI吗? #
10932次浏览 103人参与
# 说说你知道的学历厂 #
19956次浏览 120人参与
# 总结:哪家公司面试体验感最好 #
51466次浏览 367人参与
# 学历贬值真的很严重吗? #
21648次浏览 161人参与
# 面试尴尬现场 #
15584次浏览 101人参与
# 入职第一天,你准备什么时候下班 #
62838次浏览 380人参与
# 大学生该如何认清当下的就业环境? #
88665次浏览 567人参与
# 下班后的时间你怎么安排 #
5014次浏览 57人参与
# 打工人的工作餐日常 #
48582次浏览 362人参与
# 哪些公司校招卡第一学历 #
61783次浏览 234人参与
# 哪一瞬间觉得自己长大了 #
5191次浏览 85人参与
# 社会教会你的第一课 #
21611次浏览 272人参与
# 你认为小厂实习有用吗? #
7923次浏览 79人参与
# 你觉得第一学历对求职有影响吗? #
92874次浏览 668人参与
# 研究所笔面经互助 #
75376次浏览 470人参与