L3-037 夺宝大赛

Java (javac)
时间限制
800 ms
内存限制
256 MB
其他编译器
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB

题目描述：

夺宝大赛的地图是一个由 $\times m$ 个方格子组成的长方形，主办方在地图上标明了所有障碍、以及大本营宝藏的位置。参赛的队伍一开始被随机投放在地图的各个方格里，同时开始向大本营进发。所有参赛队从一个方格移动到另一个无障碍的相邻方格（“相邻”是指两个方格有一条公共边）所花的时间都是 1 个单位时间。但当有多支队伍同时进入大本营时，必将发生火拼，造成参与火拼的所有队伍无法继续比赛。大赛规定：最先到达大本营并能活着夺宝的队伍获得胜利。
假设所有队伍都将以最快速度冲向大本营，请你判断哪个队伍将获得最后的胜利。

输入格式：
输入首先在第一行给出两个正整数 $m$ 和 $n$ $\le 100）$ ，随后 $m$ 行，每行给出 $n$ 个数字，表示地图上对应方格的状态： $1$ 表示方格可通过； $0$ 表示该方格有障碍物，不可通行； $2$ 表示该方格是大本营。题目保证只有 $1$ 个大本营。
接下来是参赛队伍信息。首先在一行中给出正整数 $\times n / 2）$ ，随后 $k$ 行，第 $\le i \le k）$ 行给出编号为 $i$ 的参赛队的初始落脚点的坐标，格式为 x y。这里规定地图左上角坐标为 1 1，右下角坐标为 n m，其中 n 为列数，m 为行数。注意参赛队只能在地图范围内移动，不得走出地图。题目保证没有参赛队一开始就落在有障碍的方格里。

输出格式：
在一行中输出获胜的队伍编号和其到达大本营所用的单位时间数量，数字间以 1 个空格分隔，行首尾不得有多余空格。若没有队伍能获胜，则在一行中输出 No winner.

输入样例 1：
5 7
1 1 1 1 1 0 1
1 1 1 1 1 0 0
1 1 0 2 1 1 1
1 1 0 0 1 1 1
1 1 1 1 1 1 1
7
1 5
7 1
1 1
5 5
3 1
3 5
1 4
输出样例 1：
7 6
样例 1 说明：
七支队伍到达大本营的时间顺次为：7、不可能、5、3、3、5、6，其中队伍 4 和 5 火拼了，队伍 3 和 6 火拼了，队伍 7 比队伍 1 早到，所以获胜。

输入样例 2：
5 7
1 1 1 1 1 0 1
1 1 1 1 1 0 0
1 1 0 2 1 1 1
1 1 0 0 1 1 1
1 1 1 1 1 1 1
7
7 5
1 3
7 1
1 1
5 5
3 1
3 5
输出样例 2：
No winner.

给定一张地图，在给定k个队伍，问第一个到达大本营且没有冲突的队伍是哪队。输出队伍编号以及到达时间。如果都冲突，输出No winner.

emmmmmmm

先求从大本营开始到达每个点的步数是多少？

然后使用数组，存储每个步数上的队伍编号是多少。

如果当前位置值为0，那么表示当前步数没有队伍；
如果当前位置值为-1，那么表示当前步数有多个队伍同时到达，会产生冲突。
否则就表示，当前步数队伍到达的编号

java">import java.io.*;
import java.util.*;public class Main
{static int dxy[][] ={{ -1, 0 },{ 0, 1 },{ 1, 0 },{ 0, -1 } };static int N = (int) 1e2 + 10;static int map[][] = new int[N][N]; // 存储地图static int d[][] = new int[N][N]; // 存储从大本营到每个点的步数static int res[] = new int[N * N]; // 存储步数的编号static int n, m;// 判断当前位置是否在地图中static boolean check(int x, int y){return (1 <= x && x <= n) && (1 <= y && y <= m);}static void bfs(int startX, int startY){LinkedList<edge> li = new LinkedList<edge>();li.add(new edge(startX, startY));while (li.size() > 0){edge t = li.poll();int x = t.x;int y = t.y;for (int i = 0; i < 4; i++){int dx = x + dxy[i][0];int dy = y + dxy[i][1];// 如果当前点在地图上，以及当前点可以走，以及当前点没有走过if (check(dx, dy) && map[dx][dy] != 0 && d[dx][dy] == 0){d[dx][dy] = d[x][y] + 1; // 更新步数li.add(new edge(dx, dy));}}}}public static void main(String[] args){n = sc.nextInt();m = sc.nextInt();int x = 0, y = 0;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){map[i][j] = sc.nextInt();// 当前点是大本营if (map[i][j] == 2){x = i;y = j;}}}bfs(x, y); // 计算从大本营开始，到达每个点的步数是多少int k = sc.nextInt();for (int i = 1; i <= k; i++){// 注意先输入列，在输入行y = sc.nextInt();x = sc.nextInt();int t = d[x][y]; // 大本营达到当前点的步数// 如果当前大本营能走到if (t > 0){// 如果当前步数没走过if (res[t] == 0) res[t] = i; // 当前步数的编号设为i// 如果当前点走过else res[t] = -1; // 那么当前步数就会产生冲突}}boolean f = true; // 是否有队伍没有获胜for (int i = 1; i <= n * m; i++){// 如果当前步数的编号存在，则当前队伍获胜if (res[i] > 0){out.println(res[i] + " " + i);f = false;break;}}// 没有队伍获胜，则输出No winner.if (f) out.println("No winner.");out.flush();out.close();}static class edge{int x, y;public edge(int x, int y){this.x = x;this.y = y;}}static Scanner sc = new Scanner(System.in);static PrintWriter out = new PrintWriter(System.out);}