做网站需要了解哪些,临清网站推广,制作音乐的软件免费,酷站网素材题目#xff1a;
宝宝和妈妈参加亲子游戏#xff0c;在一个二维矩阵#xff08;N*N#xff09;的格子地图上#xff0c;宝宝和妈妈抽签决定各自
的位置#xff0c;地图上每个格子有不同的Q糖果数量#xff0c;部分格子有障碍物。
游戏规则Q是妈妈必须在最短的时间
宝宝和妈妈参加亲子游戏在一个二维矩阵N*N的格子地图上宝宝和妈妈抽签决定各自
的位置地图上每个格子有不同的Q糖果数量部分格子有障碍物。
游戏规则Q是妈妈必须在最短的时间每个单位时间只能走一步到达宝宝的位置路上的
所有糖果都可以拿走不能走障碍物的格子只能上下左右走。
请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果优先考虑最短时间到达的情况下尽
可能多拿糖果。
输入描述
第一行输入为N, N标识二维矩阵的大小
之后N行每行有N个值表格矩阵每个位置的值
其中
- 3妈妈
- 2宝宝
- 1障碍 0糖果数0表示没有糖果但是可以走
输出描述
输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果行末无多余空格
备注
地图最大50*50
示例1
输入
4
3 2 1 -3
1 -1 1 1
1 1 -1 2
-2 1 2 3
输出
9
说明
此地图有两条最短路径Q可到宝宝位置, 都是最短路径6步但先向下再向左可以拿到9个糖
果
示例2
输入
4
3 2 1 -3
-1 -1 1 1
1 1 -1 2
-2 1 -1 3
输出
-1
说明
此地图妈妈无法到达宝宝位置 题解
图求最短路径采用BFS搜索关于BFS推荐观看BFS广搜解决迷宫问题_哔哩哔哩_bilibili
看完基本就清楚BFS算法原理了。
这题里面因为有糖果数目所以这边采用的方法是如果下一步能走到终点那么终点位置的visit[endx][endy]不设置为1.这样其他方案走到终点的话也能加入进队列里面。但是由于队列里面取首元素是终点的话那么就不会往下找了所以搜索记录的应该也都是比较短的路线。然后再依旧采用一个List记录到终点的步数一个Map记录到终点的步数和糖果数的结果。最后找到最少的步数对应的最多糖果数就可以了。
代码
import java.util.*;public class FindCandy {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n Integer.valueOf(sc.nextLine());int nums[][] new int[n][n];int stratPosX Integer.MIN_VALUE;int stratPosY Integer.MIN_VALUE;int childPosX Integer.MIN_VALUE;int childPosY Integer.MIN_VALUE;int visited[][] new int[n][n];for (int i 0; i n; i) {String path[] sc.nextLine().split( );for (int j 0; j n; j) {visited[i][j] 0;nums[i][j] Integer.valueOf(path[j]);if (nums[i][j] -3) {stratPosX i;stratPosY j;visited[i][j] 1;}if (nums[i][j] -2) {childPosX i;childPosY j;}}}int[][] directions {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};QueueSteps queue new LinkedList();Steps firstStep new Steps(stratPosX, stratPosY, 0, 0);visited[stratPosX][stratPosY] 1;Steps endStep new Steps(childPosX, childPosY, 0, 0);queue.offer(firstStep);ListInteger finalRoteSteps new ArrayList();MapInteger, ListInteger stepCandyMap new HashMap();boolean hasRoote false;while (!queue.isEmpty()) {Steps frontStep ((LinkedListSteps) queue).getFirst();if (frontStep.x endStep.x firstStep.y endStep.y) {hasRoote true;continue;}for (int i 0; i 4; i) {int newX frontStep.x directions[i][0];int newY frontStep.y directions[i][1];if (newX 0 newX n newY 0 newY n nums[newX][newY] ! -1 visited[newX][newY] 0) {
// System.out.println(newX newX newY newY candy nums[newX][newY]);Steps nextStep new Steps();if (newX endStep.x newY endStep.y) {nextStep new Steps(newX, newY, frontStep.getStep() 1, frontStep.getCandy());queue.offer(nextStep);finalRoteSteps.add(nextStep.step);ListInteger candyList stepCandyMap.containsKey(nextStep.step) ? stepCandyMap.get(nextStep.step) :new ArrayList();if (!candyList.contains(nextStep.candy)) {candyList.add(nextStep.candy);}stepCandyMap.put(nextStep.step, candyList);hasRoote true;} else {nextStep new Steps(newX, newY, frontStep.getStep() 1, frontStep.getCandy() nums[newX][newY]);visited[newX][newY] 1;queue.offer(nextStep);}}}((LinkedListSteps) queue).pollFirst();}if (hasRoote) {Collections.sort(finalRoteSteps);ListInteger candys stepCandyMap.get(finalRoteSteps.get(0));Collections.sort(candys);System.out.println(candys.get(candys.size() - 1));} else {System.out.println(-1);}}
}class Steps {int x;int y;int step;int candy;public Steps() {}public Steps(int x, int y, int step, int candy) {this.x x;this.y y;this.step step;this.candy candy;}public int getX() {return x;}public void setX(int x) {this.x x;}public int getY() {return y;}public void setY(int y) {this.y y;}public int getStep() {return step;}public void setStep(int step) {this.step step;}public int getCandy() {return candy;}public void setCandy(int candy) {this.candy candy;}
}验证
