L2-013 红色警报 java

### L2-013 红色警报 Java 编程解决方案 #### 问题描述 L2-013红色警报涉及在一个网格图中找到最短路径，使得经过的格子颜色变化次数最少。此问题可以转换成一种特殊的最短路径求解问题。 #### 数据结构设计 为了高效处理这个问题，采用广度优先搜索(BFS)算法来遍历整个地图，并记录到达每一个位置所需的最小颜色变换次数。定义一个队列用于存储待访问节点的信息以及当前的颜色状态和步数。 ```java class Node { int x, y; // 当前坐标 String color; // 当前所处方块的颜色 int steps; // 到达当前位置所需改变颜色的数量 public Node(int x, int y, String color, int steps){ this.x = x; this.y = y; this.color = color; this.steps = steps; } } ``` #### 初始化设置 读取输入数据并初始化起点的位置及其初始属性（即起始点的颜色）。创建一个布尔数组`visited[][][]`用来标记已经访问过的节点以防止重复计算。该三维数组的第一维表示横坐标，第二维表示纵坐标，第三维则对应于不同可能的颜色种类。 #### 广度优先搜索实现 通过BFS逐层扩展相邻未访问结点直到终点为止。对于每个新加入到队列中的元素，更新其对应的已访问标志位，并检查是否达到了目的地。如果找到了一条通路，则返回此时累计的变化次数作为最终结果；如果没有可行路线连接源点至汇点，则输出特定提示信息表明无法完成任务。 ```java import java.util.*; public class RedAlert { private static final int MAXN = 105; private static boolean visited[MAXN][MAXN][8]; // 假设有7种不同的颜色加上空白 private static char map[MAXN][MAXN]; private static List<Node> getNextNodes(Node node){ ArrayList<Node> res = new ArrayList<>(); // 定义四个方向上的移动方式 int dx[] = {-1, 0, 1, 0}; int dy[] = {0, -1, 0, 1}; for (int i=0;i<4;++i){ int nx=node.x+dx[i], ny=node.y+dy[i]; if(nx>=0 && nx<N && ny>=0 && ny<M){ if(!map[nx][ny].equals("*")&&!visited[nx][ny][getColorIndex(node.color)]){ res.add(new Node(nx, ny,map[nx][ny],node.steps+(node.color.equals(map[nx][ny])?0:1))); } } } return res; } public static void main(String args[]) throws Exception{ Scanner sc=new Scanner(System.in); N=sc.nextInt(); M=sc.nextInt(); K=sc.nextInt(); Queue<Node> q =new LinkedList<>(); while(K-->0){ Arrays.fill(visited,false); String startColor = sc.next(); int startX = sc.nextInt()-1,startY = sc.nextInt()-1,endX = sc.nextInt()-1,endY = sc.nextInt()-1; for(int i=0;i<N;i++) for(int j=0;j<M;j++){ map[i][j]=sc.next().charAt(0); } q.offer(new Node(startX,startY,startColor,0)); while (!q.isEmpty()){ Node curNode=q.poll(); if(curNode.x==endX&&curNode.y==endY){ System.out.println(curNode.steps); break; } List<Node> nexts=getNextNodes(curNode); for(Node n :nexts){ visited[n.x][n.y][getColorIndex(n.color)]=true; q.offer(n); } } if(q.isEmpty())System.out.println(-1); } } private static int getColorIndex(String s){ switch(s){ case "R":return 0; case "G":return 1; case "B":return 2; default:return 7;//假设其他情况都映射到最后一位 } } } ```