Atcoder ABC339 D - Synchronized Players

本文主要是介绍Atcoder ABC339 D - Synchronized Players，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Synchronized Players（同步的球员）

时间限制：4s 内存限制：1024MB

【原题地址】

所有图片源自Atcoder，题目译文源自脚本Atcoder Better!

点击此处跳转至原题

【问题描述】

在这里插入图片描述

【输入格式】

在这里插入图片描述

【输出格式】

在这里插入图片描述

【样例1】

【样例输入1】

5
....#
#..#.
.P...
..P..
....#

【样例输出1】

【样例说明1】

在这里插入图片描述

【样例2】

【样例输入2】

2
P#
#P

【样例输出2】

-1

【样例3】

【样例输入3】

10
..........
..........
..........
..........
....P.....
.....P....
..........
..........
..........
..........

【样例输出3】

【解题思路】

老汉使用到的是BFS的解题方式

本题是求两点重合的最小操作数，不能重合则输出 -1 。
设两点坐标分别为 ( i1 , j1 ) 、( i2 , j2 )，将这两个坐标用四个维度的 ( i1 , j1 , i2 , j2 ) 坐标来表示，当 i1 = i2 , j1 = j2 时，才是答案所要求的情况，初始时两点错开，只有利用好棋子遇到障碍物和边界无法继续移动的特性，才能达成目的，用 BFS 搜索最短路径，并且枚举出遇到边界和障碍物的情况下坐标的变化，最早遇到重合的情况就是答案，如果遍历了整个过程下来依然没有获取到答案，则输出 -1 。

代码注释有详细过程

【代码】

package ABC339_D_SynchronizedPlayers;import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {// x、y坐标移动方向int[] dx = { 1, 0, -1, 0 };int[] dy = { 0, 1, 0, -1 };public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt();// 存放对应位置摆放情况char[][] cs = new char[n][n];for (int i = 0; i < n; i++) {cs[i] = scan.next().toCharArray();}// 头结点，用于bfs起始点Coord cod = new Coord();// 判断当前位置是否被遍历boolean[][][][] blank = new boolean[n][n][n][n];// 初始化codboolean bool = true;cod.res = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (cs[i][j] == 'P') {if (bool) {cod.x1 = i;cod.y1 = j;bool = false;} else {cod.x2 = i;cod.y2 = j;break;}}}}Queue<Coord> q = new LinkedList<Coord>();// 将起始点加入队列q.add(cod);Main mi = new Main();mi.bfs(q, blank, cs);scan.close();}// bfs遍历求最小操作数public void bfs(Queue<Coord> q, boolean[][][][] blank, char[][] cs) {// 存放边界nint n = blank.length;int ans = -1;while (!q.isEmpty()) {Coord cod = q.poll();// 当符合答案要求时，输出结果if (cod.x1 == cod.x2 && cod.y1 == cod.y2) {ans = cod.res;break;}for (int i = 0; i < 4; i++) {// 计算正常情况的下一坐标int xa = cod.x1 + dx[i], xb = cod.x2 + dx[i];int ya = cod.y1 + dy[i], yb = cod.y2 + dy[i];Coord coord = new Coord();// 操作步数等于上一步数加一coord.res = cod.res + 1;// 判断1点坐标变化// 未遇到边界或障碍时坐标正常更新，否则不变if (xa >= 0 && xa < n && ya >= 0 && ya < n && cs[xa][ya] != '#') {coord.x1 = xa;coord.y1 = ya;} else {coord.x1 = cod.x1;coord.y1 = cod.y1;}// 判断2点坐标变化// 未遇到边界或障碍时坐标正常更新，否则不变if (xb >= 0 && xb < n && yb >= 0 && yb < n && cs[xb][yb] != '#') {coord.x2 = xb;coord.y2 = yb;} else {coord.x2 = cod.x2;coord.y2 = cod.y2;}// 当下一点为空格时，添加进队列if (!blank[coord.x1][coord.y1][coord.x2][coord.y2]) {q.add(coord);// 标记为被访问blank[coord.x1][coord.y1][coord.x2][coord.y2] = true;}}}System.out.println(ans);}
}class Coord {int x1, y1, x2, y2, res;public Coord() {}
}