聚餐地计算（华为od机考题）
一、题目
1.原题
小华和小为是很要好的朋友，他们约定周末一起吃饭。
通过手机交流，
他们在地图上选择了多个聚餐地点
（由于自然地形等原因，部分聚餐地点不可达），
求小华和小为都能到达的聚餐地点有多少个？
2.题目理解
考点：[广搜, 矩阵, 并查集]
二、思路与代码过程
1.思路
输入：
地图map（包含餐厅1，可移动空间0，障碍物-1）；
小华和小为出发位置。
计算过程：
使用队列初始存储出发位置，对方向数组进行遍历，（BFS），得到可以抵达的餐厅的位置数组表，将小华和小为的进行相同值筛选后得到都可以抵达的餐厅位置数组，对数组长度进行输出即可。
2.代码过程
①main函数
public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("请输入地图长宽：");int m = sc.nextInt();int n = sc.nextInt();System.out.println("请输入地图（0：正常通行；-1：障碍；1：餐厅）：");int[][] map = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {map[i][j] = sc.nextInt();}}System.out.println("请输入小华位置：");int[] posH = new int[2];posH[0] = sc.nextInt();posH[1] = sc.nextInt();System.out.println("请输入小为位置：");int[] posW = new int[2];posW[0] = sc.nextInt();posW[1] = sc.nextInt();ArrayList<int[]>HCr = CountArrival(posH,map);ArrayList<int[]>WCr = CountArrival(posW,map);ArrayList<int[]>HWCR = CalBothCan(HCr,WCr);System.out.println("小华和小为都能到达的聚餐地点有："+HWCR.size()+"个。");}②CalBothCan
private static ArrayList<int[]> CalBothCan(ArrayList<int[]> hcr, ArrayList<int[]> wcr) {ArrayList<int[]> BR = new ArrayList<>();while (BR.size() < Math.min(hcr.size(), wcr.size())) {for (int[] i : hcr) {for (int[] j : wcr) {if (Arrays.equals(i, j)) {BR.add(i);}}}}return BR;}③方向数组
static int[][] DIRECTION ={{0,1},{1,0},{0,-1},{-1,0}};//方向数组④CountArrival
private static ArrayList<int[]> CountArrival(int[] pos, int[][] map) {boolean[][] visited = new boolean[map.length][map[0].length];//抵达标记防止重复Queue<int[]> Q = new LinkedList<>();Q.add(pos);visited[pos[0]][pos[1]] = true;ArrayList<int[]> CR = new ArrayList<>();while(!Q.isEmpty()) {int[] cur = Q.poll();visited[cur[0]][cur[1]] = true;for (int[] direction : DIRECTION) {int x = cur[0] + direction[0];int y = cur[1] + direction[1];if (x >= 0 && y >= 0 && x < map.length && y < map[0].length&&!visited[x][y]) {//在边界内if (map[x][y] == 0) {Q.add(new int[]{x,y});visited[x][y] = true;}if (map[x][y] == 1) {Q.add(new int[]{x,y});CR.add(new int[]{x,y});visited[x][y] = true;}if (map[x][y] == -1) {continue;}}}}return CR;}三、运行结果
1.运行截图
2.完整代码
import java.util.*;public class test39 {public static void main(String[] args) {///*Scanner sc = new Scanner(System.in);System.out.println("请输入地图长宽：");int m = sc.nextInt();int n = sc.nextInt();System.out.println("请输入地图（0：正常通行；-1：障碍；1：餐厅）：");int[][] map = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {map[i][j] = sc.nextInt();}}//System.out.println(Arrays.deepToString(map));System.out.println("请输入小华位置：");int[] posH = new int[2];posH[0] = sc.nextInt();posH[1] = sc.nextInt();System.out.println("请输入小为位置：");int[] posW = new int[2];posW[0] = sc.nextInt();posW[1] = sc.nextInt();//*//*int[][] map = {{0,-1,-1,1},{0,1,-1,0},{-1,0,1,0},{0,-1,0,0}};int[] posH = {0,0};int[] posW = {3,3};*/ArrayList<int[]>HCr = CountArrival(posH,map);ArrayList<int[]>WCr = CountArrival(posW,map);ArrayList<int[]>HWCR = CalBothCan(HCr,WCr);System.out.println("小华和小为都能到达的聚餐地点有："+HWCR.size()+"个。");}private static ArrayList<int[]> CalBothCan(ArrayList<int[]> hcr, ArrayList<int[]> wcr) {ArrayList<int[]> BR = new ArrayList<>();while (BR.size() < Math.min(hcr.size(), wcr.size())) {for (int[] i : hcr) {for (int[] j : wcr) {if (Arrays.equals(i, j)) {BR.add(i);}}}}return BR;}static int[][] DIRECTION ={{0,1},{1,0},{0,-1},{-1,0}};//方向数组private static ArrayList<int[]> CountArrival(int[] pos, int[][] map) {boolean[][] visited = new boolean[map.length][map[0].length];//抵达标记防止重复Queue<int[]> Q = new LinkedList<>();Q.add(pos);visited[pos[0]][pos[1]] = true;ArrayList<int[]> CR = new ArrayList<>();while(!Q.isEmpty()) {int[] cur = Q.poll();visited[cur[0]][cur[1]] = true;for (int[] direction : DIRECTION) {int x = cur[0] + direction[0];int y = cur[1] + direction[1];if (x >= 0 && y >= 0 && x < map.length && y < map[0].length&&!visited[x][y]) {//在边界内if (map[x][y] == 0) {Q.add(new int[]{x,y});visited[x][y] = true;}if (map[x][y] == 1) {Q.add(new int[]{x,y});CR.add(new int[]{x,y});visited[x][y] = true;}if (map[x][y] == -1) {continue;}}}}/*System.out.println("\n可抵达餐厅有：");for (int[] element : CR) {System.out.print(Arrays.toString(element));}System.out.println();*/return CR;}
}