关注
第一题动态规划解法,代码没优化,中间还有调试用的输出,额,有点长。大体思想,先求出(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]));
}
}
}
查看原帖
点赞 评论
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 你认为小厂实习有用吗? #
14025次浏览 186人参与
# 面试官是我前女友 #
107052次浏览 731人参与
# 实习生的蛐蛐区 #
40522次浏览 329人参与
# 当你面对裁员会如何? #
275982次浏览 2438人参与
# 计算机有哪些岗位值得去? #
13042次浏览 134人参与
# lastday知无不言 #
56915次浏览 460人参与
# 在职场上,你最讨厌什么样的同事 #
14511次浏览 150人参与
# 推荐一首陪你工作的歌吧 #
14039次浏览 97人参与
# 说说你知道的学历厂 #
28454次浏览 178人参与
# 你找工作的时候用AI吗? #
15000次浏览 193人参与
# 下班后的时间你怎么安排 #
7546次浏览 111人参与
# 哪一瞬间觉得自己长大了 #
7301次浏览 167人参与
# 携程求职进展汇总 #
559478次浏览 4258人参与
# 面试尴尬现场 #
24070次浏览 164人参与
# 工作后会跟朋友渐行渐远吗 #
30077次浏览 216人参与
# 中核求职进展汇总 #
20165次浏览 152人参与
# 社会教会你的第一课 #
29540次浏览 396人参与
# 多益网络工作体验 #
49693次浏览 280人参与
# 虾皮求职进展汇总 #
244210次浏览 1797人参与
# 神州信息工作体验 #
16060次浏览 75人参与