原题链接:蓝桥杯2018年第九届真题-迷宫与陷阱
解题思路:
BFS
注意事项:
条件找全
参考代码:
import java.util.*; public class Main { static int N; static char[][] map; static int K; static int step; static boolean[][][] vis; static int[] dx = { -1, 0, 1, 0 }; static int[] dy = { 0, -1, 0, 1 }; public static void main(String[] args) { Scanner in = new Scanner(System.in); N = in.nextInt(); K = in.nextInt(); int ans = -1; map = new char[N + 2][N + 2]; vis = new boolean[N + 2][N + 2][11]; String tempStr = in.nextLine(); for (int i = 1; i <= N; i++) { tempStr = in.nextLine(); for (int j = 0; j < tempStr.length(); j++) map[i][j + 1] = tempStr.charAt(j); } Main main = new Main(); Queue<Node> queue = new LinkedList<Node>(); queue.offer(map[1][1] == '.' ? main.new Node(1, 1, 0, 0) : main.new Node(1, 1, 0, K)); if(map[1][1] == '.') vis[1][1][0]=true; else vis[1][1][K]=true; while(!queue.isEmpty()) { Node tempNode = queue.poll(); if(tempNode.x==N&&tempNode.y==N) { ans = tempNode.step; break; } for(int i=0;i<4;i++) { int x = tempNode.x+dx[i]; int y = tempNode.y+dy[i]; if(map[x][y]!='#'&&x>=1&&x<=N&&y>=1&&y<=N) { if(map[x][y]=='X'&&tempNode.invincible>0&&vis[x][y][tempNode.invincible-1]==false) { vis[x][y][tempNode.invincible-1]=true; queue.offer(main.new Node(x,y,tempNode.step+1,tempNode.invincible-1)); }else if(map[x][y]=='%'&&vis[x][y][K]==false) { vis[x][y][K]=true; queue.offer(main.new Node(x,y,tempNode.step+1,K)); }else if(map[x][y]=='.'&&tempNode.invincible==0&&vis[x][y][0]==false) { vis[x][y][0]=true; queue.offer(main.new Node(x,y,tempNode.step+1,0)); }else if(map[x][y]=='.'&&tempNode.invincible>0&&vis[x][y][tempNode.invincible-1]==false) { vis[x][y][tempNode.invincible-1]=true; queue.offer(main.new Node(x,y,tempNode.step+1,tempNode.invincible-1)); } } } } System.out.println(ans); } class Node { int x; int y; int step; int invincible; public Node(int x, int y, int step, int invincible) { super(); this.x = x; this.y = y; this.step = step; this.invincible = invincible; } } }
0.0分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复