[编程题]地牢逃脱
- 热度指数：25924 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
给定一个 n 行 m 列的地牢，其中 '.' 表示可以通行的位置，'X' 表示不可通行的障碍，牛牛从 (x0 , y0 ) 位置出发，遍历这个地牢，和一般的游戏所不同的是，他每一步只能按照一些指定的步长遍历地牢，要求每一步都不可以超过地牢的边界，也不能到达障碍上。地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况下，他需要多少步才可以离开这个地牢。
输入描述:
每个输入包含 1 个测试用例。每个测试用例的第一行包含两个整数 n 和 m（1 <= n, m <= 50），表示地牢的长和宽。接下来的 n 行，每行 m 个字符，描述地牢，地牢将至少包含两个 '.'。接下来的一行，包含两个整数 x0, y0，表示牛牛的出发位置（0 <= x0 < n, 0 <= y0 < m，左上角的坐标为 （0, 0），出发位置一定是 '.'）。之后的一行包含一个整数 k（0 < k <= 50）表示牛牛合法的移动方式的数量，接下来的 k 行，每行两个整数 dx, dy 表示每次可选择移动的行和列步长（-50 <= dx, dy <= 50）
输出描述:
输出一行一个数字表示最坏情况下需要多少次移动可以离开地牢，如果永远无法离开，输出 -1。以下测试用例中，牛牛可以上下左右移动，在所有可通行的位置.上，地牢出口如果被设置在右下角，牛牛想离开需要移动的次数最多，为3次。
示例1
输入
3 3 ... ... ... 0 1 4 1 0 0 1 -1 0 0 -1
输出
3
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while (in.hasNext()) {//注意while处理多个case
int x=in.nextInt();
int y=in.nextInt();
char[][] points=new char[x][y];
int[][] tar=new int[x][y];
for(int i=0;i<x;i++){
String str=in.next();
points[i]=str.toCharArray();
}
int startx=in.nextInt();
int starty=in.nextInt();
int k=in.nextInt();
int[] stepx=new int[k];
int[] stepy=new int[k];
for(int i=0;i<k;i++){
stepx[i]=in.nextInt();
stepy[i]=in.nextInt();
}
Queue<Integer> xqueue=new LinkedList<Integer>();
Queue<Integer> yqueue=new LinkedList<Integer>();
//引入队列是为了遍历到最后不能走为止
xqueue.add(startx);
yqueue.add(starty);
tar[startx][starty]=1; //起始点访问标记；1表示已经访问
while(!xqueue.isEmpty()&&!yqueue.isEmpty()){
startx=xqueue.remove(); //取队首
starty=yqueue.remove();
for(int i=0;i<k;i++){
if(startx+stepx[i]<x&&startx+stepx[i]>=0&&starty+stepy[i]<y&&starty+stepy[i]>=0) //不出界
if(tar[startx+stepx[i]][starty+stepy[i]]==0){
if(points[startx+stepx[i]][starty+stepy[i]]=='.'){
tar[startx+stepx[i]][starty+stepy[i]]=tar[startx][starty]+1;
xqueue.add(startx+stepx[i]);
yqueue.add(starty+stepy[i]);
}
else
tar[startx+stepx[i]][starty+stepy[i]]=-1; //访问点为X
}
}
}
int max=0;
int getRoad=1;
for(int i=0;i<x;i++)
for(int j=0;j<y;j++){
if(points[i][j]=='.'&&tar[i][j]==0){
getRoad=0; //有存在没有被访问的“.”说明不能遍历完全，有些出口到不了。
}
max=Math.max(max, tar[i][j]);
}
if(getRoad==0)
System.out.println(-1);
else
System.out.println(max-1);
}
}
}
编辑于 2016-08-14 12:03:46
回复(5)
仔细读题可以发现 题目要求的就是从出发点宽度优先搜索不走回头路 能够到达的最远距离；
按测试样例为例
...
...
...
第0步为起点(0, 1)
第一步能够到达的点为(0, 0) (1, 1) (0, 2)
第二步能到达的点（去掉重复）为(1, 0) (2, 1) (1, 2)
第三步能到达的点为(2, 0) (2, 2)
此时第四部无论怎么走都会重复 所以最长步数为3
但是这种解法忽略了一种“孤岛的情况” 例如
X.X
...
XXX
X.X
此时选择最下面这个“.”即为最差情况 答案-1
因此在宽度优先搜索结束后要判断是否有孤岛存在
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
//常量区
const int maxn = 50 + 5;
int taken[maxn][maxn], n, m, k, sx[maxn], sy[maxn];
int x_0, y_0;
char ma[maxn][maxn];
queue<int> qx[maxn];
queue<int> qy[maxn];
//函数区
int bfs(){
qx[0].push(x_0); qy[0].push(y_0);
taken[x_0][y_0] = 1;
int d;
for(d = 0; ; d++){
while(!qx[d].empty()){
int tx = qx[d].front(); qx[d].pop();
int ty = qy[d].front(); qy[d].pop();
for(int i=0;i<k;i++){
if((tx+sx[i]>=0) && (tx+sx[i])<n && (ty+sy[i]>=0) && (ty+sy[i])<m &&
taken[tx+sx[i]][ty+sy[i]]==0 && ma[tx+sx[i]][ty+sy[i]] != 'X'){
qx[d+1].push(tx+sx[i]);
qy[d+1].push(ty+sy[i]);
taken[tx+sx[i]][ty+sy[i]] = 1;
}
}
}
if(qx[d+1].empty()) break;
}
return d;
}
//main函数
int main(){
scanf("%d%d", &n, &m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++) scanf(" %c", &ma[i][j]);
scanf("%d%d%d", &x_0, &y_0, &k);
for(int i=0;i<k;i++) scanf("%d%d", &sx[i], &sy[i]);
int ans = bfs(); //宽度优先搜索 返回可以行走的最长步数
//判断是否有孤岛 即无法访问到但是可通行的点
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(taken[i][j] == 0 && ma[i][j] == '.'){
printf("-1\n"); //若有孤岛 选择孤岛为终点 无法离开 此时是最坏情况
return 0;
}
if(ans == 0) cout<<-1<<endl;//只有起点可以走 其他都是'X'的情况
else cout<<ans<<endl;
return 0;
}
编辑于 2018-10-05 21:54:23
回复(0)
这道题说得很不清楚，正常理解的话，需要判断是否路径可达，
比如
OXO
XXO
OOO
那么从（2，2）是不可达（0，0）的。而且即使可达，路径还可能大于L1距离。
但是看AC的答案应该是指，瞬间移动，即不管中间是否有障碍物，只要目标位置不是障碍物，就可以移动到该位置。
所以，不想说啥了，出题人，语文水平有待提高
发表于 2016-08-09 17:19:56
回复(3)
#include <iostream>
#include <queue>
#include <string.h>
const int T = 50;
char DL[T][T];
int n = 0;
int m = 0;
int x0 = 0;
int y0 = 0;
int k = 0;
int dx[T];
int dy[T];
int visited[T][T]; //记录最短到达步数
int main() {
std::cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
std::cin >> DL[i][j];
}
}
std::cin >> x0 >> y0 >> k;
for (int i = 0; i < k; ++i) {
std::cin >> dx[i] >> dy[i];
}
memset(visited, 0, sizeof(visited));
visited[x0][y0] = 1; //起始步数为1,0表示未访问
std::queue<std::pair<int, int> > q;
q.push(std::pair<int, int>(x0, y0));
int curx = 0;
int cury = 0;
int nextx = 0;
int nexty = 0;
while (!q.empty()) {
curx = q.front().first;
cury = q.front().second;
q.pop();
for (int j = 0; j < k; ++j) {
nextx = curx + dx[j];
nexty = cury + dy[j];
if (nextx >= 0 && nextx < n && nexty >= 0 && nexty < m && visited[nextx][nexty] == 0) {
if (DL[nextx][nexty] == '.') {
visited[nextx][nexty] = visited[curx][cury] + 1;
q.push(std::pair<int, int>(nextx, nexty));
}
}
}
}
int max = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (DL[i][j] == '.') {
if (visited[i][j] == 0) {
std::cout << -1;
return 0;
}
else if (visited[i][j] > max) {
max = visited[i][j];
}
}
}
}
std::cout << max-1;
return 0;
}
发表于 2017-09-01 20:13:21
回复(0)
# coding: utf-8
'''
题意可以理解为：有没有可以通行的点，但牛牛到不了（输出-1）。如果没有这样的点，牛牛可能花费最多步数是多少。
思路：计算地图里，每个点的最短到达步数。找到到不了的点，或者步数最多的点。
1. 创建3个矩阵，size都是n*m的。分别是地图矩阵 mm、步数矩阵 sm、到达矩阵 am。详见代码里的注释。*也可以把3个矩阵放到一起。
2. 设置初始点为第一轮的探索点，更新 sm 里初始点的最短步数为0，更新 am 里初始点的到达状态为1。
3. 找到从探索点一步能到达的点，且这些点可以通行并没有到达过。更新这些点的 sm 和 am。并将这些点当作下一轮的探索点。
4. 循环第3步，直到没有新一轮的探索点了。
5. 从 sm 中可以得到正确答案。
'''
def main():
line_1 = raw_input().split()
n, m = int(line_1[0]), int(line_1[1])
map_matrix = [raw_input() for i in range(n)] # 地图矩阵，'.'表示可以通行，其他表示不可通行
line_2 = raw_input().split()
x0, y0 = int(line_2[0]), int(line_2[1]) # 开始点的坐标
k = input() # 共有k种行走方式
alternative_steps = [[int(s) for s in raw_input().split()] for i in range(k)] # 可以选择的行走方式
step_matrix = [[-1] * m for i in range(n)] # 步数矩阵，记录到达该点使用最短步数。初始是-1。
arrived_matrix = [[0] * m for i in range(n)] # 到达矩阵，记录是否已经到达过该点。初始是0，表示没有到达过，
# 判断初始点是否是可达点
if map_matrix[x0][y0] != '.':
return -1
# 初始点修改为已到达的点
arrived_matrix[x0][y0] = 1
# 初始点到达步数为0
step_matrix[x0][y0] = 0
current_points = [[x0, y0]] # 第一轮所在的探索点（多个）
while len(current_points) > 0: # 如果当前探索点是0个，结束循环。
next_points = [] # 下一轮的探索点（多个）
for point in current_points:
x, y = point[0], point[1] # 一个探索点
for step in alternative_steps:
x_, y_ = x + step[0], y + step[1] # 该探索点一步能到达的点
if x_ < 0 or x_ >= n or y_ < 0 or y_ >= m: # 检查是否越界
continue
if map_matrix[x_][y_] != '.' or arrived_matrix[x_][y_] == 1: # 检查该点是否可以通行，或者已经达到过
continue
else:
step_matrix[x_][y_] = step_matrix[x][y] + 1 # 更新步数矩阵
arrived_matrix[x_][y_] = 1 # 更新到达矩阵
next_points.append([x_, y_]) # 该点添加到下一轮探索点里。
current_points = next_points
# 从步数矩阵中找到到不了的点，或者最大的步数。输出
max_step = 0
for i in range(n):
for j in range(m):
step = step_matrix[i][j]
if step == -1 and map_matrix[i][j] == '.':
return -1
if step > max_step:
max_step = step
return max_step
print main()
发表于 2017-07-11 18:20:33
回复(3)
import java.util.*;
import java.io.*;
public class Main {
/**
*关键描述：地牢的出口可能在任意某个可以通行的位置上。牛牛想知道最坏情况下，他需要多少步才可以离开这个地牢。
*这句话的意思是什么呢？结合示离，意思是在可通行的位置上，我们要选择最短路径。但是有多个可通行的位置上，我们要找最远的，若最远不可达输出-1
*这样问题就转化为最短路径问题，我们要找到最远点的最短路径。使用BFS可以实现。
*/
public static void main(String[] args) throws Exception{
String[] arrInput;
char[] arrChar;
Deque<Pointer> deque = new ArrayDeque<Pointer>();//使用双端队列做队列
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
arrInput = br.readLine().trim().split(" ");
int n = Integer.parseInt(arrInput[0]);
int m = Integer.parseInt(arrInput[1]);
int[][] arrDungeon = new int[n][m];//-1不可通行，0可以通行，整数为到达的步数
for (int i=0; i<n; i++) {
arrChar = br.readLine().trim().toCharArray();//应为连续字符没有间隔，用toCharArray转化为字符数组
for (int j=0; j<m; j++) {
if (arrChar[j] == '.') {
arrDungeon[i][j] = 0;
} else if (arrChar[j] == 'X') {
arrDungeon[i][j] = -1;
}
}
}
arrInput = br.readLine().trim().split(" ");
Pointer pointer = new Pointer();
pointer.x = Integer.parseInt(arrInput[0]);
pointer.y = Integer.parseInt(arrInput[1]);
int startxx = pointer.x;
int startyy = pointer.y;
deque.offerLast(pointer);//入队
int intStepCnt = Integer.parseInt(br.readLine().trim());
int[][] arrStep = new int[intStepCnt][2];
for (int i=0; i<intStepCnt; i++) {
arrInput = br.readLine().trim().split(" ");
arrStep[i][0] = Integer.parseInt(arrInput[0]);
arrStep[i][1] = Integer.parseInt(arrInput[1]);
}
int x = 0;
int y = 0;
int x1 = 0;
int y1 = 0;
//BFS由近及远
while (deque.size() > 0) {
Pointer pointerOne = deque.pollFirst();
x = pointerOne.x;
y = pointerOne.y;
for (int i=0; i<intStepCnt; i++) {
x1 = x + arrStep[i][0];
y1 = y + arrStep[i][1];
if (x1 >= 0 && x1 < arrDungeon.length && y1 >= 0 && y1 < arrDungeon[0].length && arrDungeon[x1][y1] == 0) {//不越界的情况
arrDungeon[x1][y1] = arrDungeon[x][y] + 1;
Pointer temp = new Pointer();
temp.x = x1;
temp.y = y1;
deque.offerLast(temp);//入队
}
}
}
int max = 0;
boolean isHaveCanNotAccessPointer = false;//标记有没有不可达点的
for (int i=0; i<n; i++) {
if (isHaveCanNotAccessPointer == true) {
break;
}
for (int j=0; j<m; j++) {
if ((i != startxx || j != startyy) && arrDungeon[i][j] == 0) {//不是起点若是0就是有不可达点
isHaveCanNotAccessPointer = true;
break;
}
if (arrDungeon[i][j] > max) {
max = arrDungeon[i][j];
}
}
}
if (isHaveCanNotAccessPointer) {
System.out.println(-1);
} else {
System.out.println(max);
}
}
static class Pointer {//坐标类
public int x;
public int y;
}
}
发表于 2018-10-29 20:52:28
回复(2)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner input=new Scanner(System.in);
while(input.hasNext()){
int n=input.nextInt();
int m=input.nextInt();
char[][] a=new char[n][m];
for(int i=0; i<n; i++){
a[i]=input.next().toCharArray();
}
int x0=input.nextInt();
int y0=input.nextInt();
int k=input.nextInt();
int[] dx=new int[k];
int[] dy=new int[k];
for(int i=0; i<k; i++){
dx[i]=input.nextInt();
dy[i]=input.nextInt();
}
int[][] f=new int[n][m];
ArrayList<Integer> x=new ArrayList<>();
ArrayList<Integer> y=new ArrayList<>();
x.add(x0); y.add(y0);
f[x0][y0]=1; //起始点访问标记；1表示已经访问
while(!x.isEmpty() && !y.isEmpty()){
int tempX=x.remove(0);
int tempY=y.remove(0);
for(int i=0; i<k; i++){
if(tempX+dx[i]>=0&&tempX+dx[i]<n&&tempY+dy[i]>=0&&tempY+dy[i]<m){ //判断是否越界
if(f[tempX+dx[i]][tempY+dy[i]]==0){
if(a[tempX+dx[i]][tempY+dy[i]]=='.'){
f[tempX+dx[i]][tempY+dy[i]]=f[tempX][tempY]+1;
x.add(tempX+dx[i]);
y.add(tempY+dy[i]);
}else{
f[tempX+dx[i]][tempY+dy[i]]=-1;
}
}
}
}
}
int max=0;
int tt=1;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(f[i][j]==0 && a[i][j]=='.')
tt=0;
else{
max=Math.max(max, f[i][j]);
}
}
}
if(tt==1)
System.out.println(max-1);
else
System.out.println(-1);
}
}
}
发表于 2018-09-03 18:37:23
回复(0)
带注释的JAVA版，研究了很久，稍微调了几次就AC了，看了别人的解答，也自己去研究了下广度优先遍历(BFS)，比如迷宫问题的解题思路。只要思路清晰了，AC很快的。
BFS的思路就是把目前能到达的点都添加到待解决队里去，相比之下DFS是先一条路走到黑，走不通了再回来。BFS这里要注意重复判断问题，避免死循环，常见的可以加个标志，被遍历过了就设flag。如果是单方向的就没有重复问题了。
import java.util.List;
import java.util.Queue;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
char[][] map = new char[n][m];//存这个地牢的信息
for(int i=0;i<n;i++){
map[i] = in.next().toCharArray();
}
int startX = in.nextInt();//起点
int startY = in.nextInt();
int k = in.nextInt();//步子数
int[][] dir = new int[k][2];//神奇的步子
for(int i=0;i<k;i++){
dir[i][0] = in.nextInt();
dir[i][1] = in.nextInt();
}
int[][] minThisPosition = new int[n][m];//到可行点的最小步数
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
minThisPosition[i][j] = Integer.MAX_VALUE;
}
}
minThisPosition[startX][startY] = 0;
class Node{//局部内部类定义一个点
int x;
int y;
Node(int x, int y){
this.x = x;
this.y = y;
}
public Node goK(int k){//尝试走第K种步子到达的节点
return new Node(x+dir[k][0],y+dir[k][1]);
}
public boolean isleagle(){//判断这个节点是不是在地牢内,是不是障碍
return x>=0&&y>=0&&x<n&&y<m&&map[x][y]=='.';
}
}
Node startNode = new Node(startX, startY);
//用队列来记录是不是所有 "." 都被处理了
Queue<Node> queue = new LinkedList<>();
queue.add(startNode);//从起点开始
while(!queue.isEmpty()){
Node now = queue.poll();
for(int i=0;i<k;i++){
Node next = now.goK(i);
if(next.isleagle()){
//这里避免了往回走，不加1也可以，就是大于等于minThisPosition[now.x][now.y]+1
if(minThisPosition[next.x][next.y]>minThisPosition[now.x][now.y]+1){
//每种步子都尝试一下，找到最小值
minThisPosition[next.x][next.y]=minThisPosition[now.x][now.y]+1;
queue.add(next);//加到队列里等待处理
}
}
}
}
int result = 0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
//找到最大值
if(map[i][j] == '.') result = Math.max(result, minThisPosition[i][j]);
}
}
//如果存在不能到达的 "." ,就会保留原来的初试值，返回-1
System.out.println(result == Integer.MAX_VALUE?-1:result );
}
}
发表于 2018-08-22 13:18:04
回复(0)
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
#define max(a,b) a>b?a:b
int Next[50][2],step[50][50],book[50][50],n,m,s,e,k,i,j,Max=-1;
char Map[50][50];
struct node{
int x,y;
node(int x,int y):x(x),y(y){}
};
int main(){
memset(step,-1,sizeof(step));
for(scanf("%d%d",&n,&m),i=0;i<n;i++) scanf("%s",Map[i]);
for(scanf("%d%d%d",&s,&e,&k),i=0;i<k;i++)
scanf("%d%d",&Next[i][0],&Next[i][1]);
queue<node> Q;
Q.push(node(s,e)),book[s][e]=1,step[s][e]=0;
while(!Q.empty()){
node head=Q.front();Q.pop();
for(i=0;i<k;i++){
int nx=head.x+Next[i][0],ny=head.y+Next[i][1];
if(nx<0||nx>=n||ny<0||ny>=m||book[nx][ny]||Map[nx][ny]!='.') continue;
book[nx][ny]=1,step[nx][ny]=step[head.x][head.y]+1,Q.push(node(nx,ny));
}
}
for(k=1,i=0;i<n;i++)
for(j=0;j<m;j++)
Map[i][j]=='.'?step[i][j]>=0?Max=max(Max,step[i][j]):k=0:Max=Max;
printf("%d\n",Max>0&&k?Max:-1);
}
发表于 2017-10-20 23:33:42
回复(0)
宽度优先搜索
从起点出发，利用BFS求到任意位置的最短距离矩阵
，其中
表示起点到&preview=true)
位置的最短距离。然后遍历这个矩阵，对于任意一个位置，如果它在地牢矩阵中可以通行，它就可以成为地牢的出口，找到这些位置的最大值就可以了。
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] params = br.readLine().split(" ");
int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]);
char[][] grid = new char[n][];
for(int i = 0; i < n; i++){
grid[i] = br.readLine().toCharArray();
}
params = br.readLine().split(" ");
int x0 = Integer.parseInt(params[0]), y0 = Integer.parseInt(params[1]);
int k = Integer.parseInt(br.readLine());
int[] dx = new int[k], dy = new int[k];
for(int i = 0; i < k; i++){
params = br.readLine().split(" ");
dx[i] = Integer.parseInt(params[0]);
dy[i] = Integer.parseInt(params[1]);
}
int maxStep = 0;
int[][] dis = bfs(grid, x0, y0, dx, dy);
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == '.'){
// 所有能走的地方都可以作为出口
maxStep = Math.max(maxStep, dis[i][j]);
}
}
}
System.out.println(maxStep == Integer.MAX_VALUE? -1: maxStep);
}
private static int[][] bfs(char[][] grid, int x0, int y0, int[] dx, int[] dy) {
int n = grid.length, m = grid[0].length;
int[][] dis = new int[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
dis[i][j] = Integer.MAX_VALUE;
}
}
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x0, y0});
dis[x0][y0] = 0;
while(!queue.isEmpty()){
int queueSize = queue.size();
for(int j = 0; j < queueSize; j++){
int[] cur = queue.poll();
int x = cur[0], y = cur[1];
for(int i = 0; i < dx.length; i++){
int x_ = cur[0] + dx[i];
int y_ = cur[1] + dy[i];
if(0 <= x_ && x_ < n && 0 <= y_ && y_ < m && grid[x_][y_] == '.'){
if(dis[x_][y_] > dis[x][y] + 1){
// 类似迪杰斯特拉算法，距离变小了就更新
dis[x_][y_] = dis[x][y] + 1;
queue.offer(new int[]{x_, y_});
}
}
}
}
}
return dis;
}
}
发表于 2022-03-04 17:24:35
回复(0)
//广度优先搜索 #include <iostream> #include <vector> #include <queue> using namespace std; typedef struct loc { int x, y; char val; bool visited; }loc; int bfs_map(vector<loc> & map, const int N, const int M, const int xStart, const int yStart, const int numSteps, const vector<int> steps); int main() { int n, m; cin >> n >> m; vector<loc> map; { loc c; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> c.val; c.visited = false; c.x = i; c.y = j; map.push_back(c); } } } int x0, y0; cin >> x0 >> y0; int k; cin >> k; vector<int> steps; { int temp; for (int i = 0; i < k*2; ++i) { cin >> temp; steps.push_back(temp); } } int result = bfs_map(map, n, m, x0, y0, k, steps); cout << result << endl; return 0; } int bfs_map(vector<loc> & map, const int N, const int M, const int xStart, const int yStart, const int numSteps, const vector<int> steps){ int result = -1; //实际上计算广度优先搜索的层数 map[xStart * M + yStart].visited = true; queue<loc> Q, Q_temp; Q.push(map[xStart * M + yStart]); while (!Q.empty()) { result++; while (!Q.empty()) { loc currentLoc = Q.front(); Q.pop(); for (int i = 0; i < numSteps; ++i) { int xNew = currentLoc.x + steps[2 * i]; int yNew = currentLoc.y + steps[2 * i + 1]; if (xNew >= 0 && xNew < N && yNew >= 0 && yNew < M && map[xNew * M + yNew].val == '.' && map[xNew * M + yNew].visited == false) { map[xNew * M + yNew].visited = true; Q_temp.push(map[xNew * M + yNew]); } } } swap(Q, Q_temp); } //永远不可能出去的情况 for (int i = 0; i < N*M; ++i) { if (map[i].val == '.' && map[i].visited != true) return -1; } if (result > 0) return result; else return - 1; }
发表于 2019-04-24 22:23:52
回复(0)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Pos {
int x;
int y;
int step;
};
int m, n;
bool ok(int x, int y, vector<vector<char>> &v)
{
if (x >= 0 && x<m && y>= 0 && y<n && v[x][y]=='.')
return true;
return false;
}
int main()
{
cin >> m >> n;
vector<vector<char>> v(m, vector<char>(n));
for (int i = 0; i<m; i++)
{
for (int j = 0; j<n; j++)
{
cin >> v[i][j];
}
}
int x0, y0;
cin >> x0 >> y0;
int stepN;
cin >> stepN;
vector<vector<int>> move(stepN, vector<int>(2));
vector<vector<int>> vRes(m, vector<int>(n, 9999));
for (int i = 0; i<stepN; i++)
{
cin >> move[i][0] >> move[i][1];
}
queue<Pos> qu;
vRes[x0][y0] = 0;
Pos start = { x0,y0,0 };
qu.push(start);
Pos now,tmp;
int x, y;
while (!qu.empty())
{
now = qu.front();
qu.pop();
for (int i = 0; i<stepN; i++)
{
x = now.x + move[i][0];
y = now.y + move[i][1];
if (ok(x, y, v) && now.step+1<vRes[x][y])
{
vRes[x][y] = now.step + 1;
tmp = { x,y,now.step + 1 };
qu.push(tmp);
}
else {
continue;
}
}
}
int maxStep = 0;
for (int i = 0; i<m; i++)
{
for (int j = 0; j<n; j++)
{
if (vRes[i][j]>maxStep && v[i][j]=='.')
maxStep = vRes[i][j];
}
}
maxStep = (maxStep == 9999) ? -1 : maxStep;
cout << maxStep << endl;
return 0;
}
发表于 2018-08-27 18:21:12
回复(1)
#-*- coding: utf8 -*-
class cell:
def __init__(self,x,y,steps):
self.x=x
self.y=y
self.steps=steps
def check(matrix,visited,x,y,n,m):
return (0<=x<n and 0<=y<m) and (matrix[x][y]=='.') and visited[x][y]==False
def maze(matrix,n,m,x,y,stepxy):
"""
最短路径bfs，最坏的情况下需要多少步逃脱，出口不定，找最短路径中最长的路径长
"""
q=[]
q.append(cell(x,y,0))
visited=[[False]*m for _ in range(n)]
visited[x][y]=True
maxsteps=0
while len(q)!=0:
elem=q.pop(0)
maxsteps=max(maxsteps,elem.steps)
for vx,vy in stepxy:
newx=elem.x+vx
newy=elem.y+vy
if check(matrix,visited,newx,newy,n,m):
q.append(cell(newx,newy,elem.steps+1))
visited[newx][newy]=True
for i in range(n):
for j in range(m):
if matrix[i][j]=='.' and visited[i][j]==False:
return -1
return maxsteps
n,m=map(int,raw_input().strip().split(' '))
matrix=[list(raw_input().strip()) for _ in range(n)]
x0,y0=map(int,raw_input().strip().split(' '))
steps=input()
stepxy=[map(int,raw_input().strip().split(' ')) for _ in range(steps)]
print maze(matrix,n,m,x0,y0,stepxy)
发表于 2018-07-30 20:20:17
回复(0)
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
int n = 0, m = 0;
int direction[][] = new int[55][2];
int dcnt;
int dis[][] = new int[55][55];
char[][] ground = new char[55][55];
public static void main(String[] args) {
Main t = new Main();
t.solve();
}
public void solve() {
Scanner in = new Scanner(System.in);
n = in.nextInt(); m = in.nextInt();
for(int i = 0; i < n; i++){
String str = in.next();
ground[i] = str.toCharArray();
}
for(int i = 0; i < n;i++){
for(int j = 0; j < m; j++){
dis[i][j] = Integer.MAX_VALUE;
}
}
int sx = in.nextInt();
int sy = in.nextInt();
dcnt = in.nextInt();
for(int i = 0; i < dcnt; i++){
direction[i][0] = in.nextInt();
direction[i][1] = in.nextInt();
}
Point start = new Point(sx, sy);
Queue<Point> q = new LinkedList();
dis[sx][sy] = 0; q.add(start);
while(q.size() != 0){
Point cur = q.poll();
for(int i = 0; i < dcnt; i++){
Point temp = cur.go(i);
if(temp.isOK()){
if(dis[temp.x][temp.y] > dis[cur.x][cur.y] + 1){
dis[temp.x][temp.y] = dis[cur.x][cur.y] + 1;
q.add(temp);
}
}
}
}
// for(int i = 0; i<n;i++){
// for(int j = 0; j <m;j++){
// System.out.print(dis[i][j] + " ");
// }
// System.out.println();
// }
int res = 0;
for(int i = 0; i < n; i++){
for(int j = 0;j < m; j++){
if(ground[i][j] =='.') res = Math.max(res,dis[i][j]);
}
}
System.out.println(res == Integer.MAX_VALUE? -1:res);
}
class Point{
private int x;
private int y;
public Point go(int dirIndex){
return new Point(this.x + direction[dirIndex][0], this.y + direction[dirIndex][1]);
}
public boolean isOK(){
return this.x >= 0 && this.y >= 0 && this.x < n && this.y < m && ground[x][y]=='.';
}
public Point(int x, int y) {
super();
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
}
import java.util.Queue;
import java.util.Scanner;
public class Main {
int n = 0, m = 0;
int direction[][] = new int[55][2];
int dcnt;
int dis[][] = new int[55][55];
char[][] ground = new char[55][55];
public static void main(String[] args) {
Main t = new Main();
t.solve();
}
public void solve() {
Scanner in = new Scanner(System.in);
n = in.nextInt(); m = in.nextInt();
for(int i = 0; i < n; i++){
String str = in.next();
ground[i] = str.toCharArray();
}
for(int i = 0; i < n;i++){
for(int j = 0; j < m; j++){
dis[i][j] = Integer.MAX_VALUE;
}
}
int sx = in.nextInt();
int sy = in.nextInt();
dcnt = in.nextInt();
for(int i = 0; i < dcnt; i++){
direction[i][0] = in.nextInt();
direction[i][1] = in.nextInt();
}
Point start = new Point(sx, sy);
Queue<Point> q = new LinkedList();
dis[sx][sy] = 0; q.add(start);
while(q.size() != 0){
Point cur = q.poll();
for(int i = 0; i < dcnt; i++){
Point temp = cur.go(i);
if(temp.isOK()){
if(dis[temp.x][temp.y] > dis[cur.x][cur.y] + 1){
dis[temp.x][temp.y] = dis[cur.x][cur.y] + 1;
q.add(temp);
}
}
}
}
// for(int i = 0; i<n;i++){
// for(int j = 0; j <m;j++){
// System.out.print(dis[i][j] + " ");
// }
// System.out.println();
// }
int res = 0;
for(int i = 0; i < n; i++){
for(int j = 0;j < m; j++){
if(ground[i][j] =='.') res = Math.max(res,dis[i][j]);
}
}
System.out.println(res == Integer.MAX_VALUE? -1:res);
}
class Point{
private int x;
private int y;
public Point go(int dirIndex){
return new Point(this.x + direction[dirIndex][0], this.y + direction[dirIndex][1]);
}
public boolean isOK(){
return this.x >= 0 && this.y >= 0 && this.x < n && this.y < m && ground[x][y]=='.';
}
public Point(int x, int y) {
super();
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
}
}
发表于 2018-03-21 16:00:34
回复(0)
# -*- coding:utf-8 -*-
n, m = map(int, raw_input().split())
A, d = [[0] * m for _ in range(n)], 0
for i in range(n):
A.append([0] * m)
s1 = raw_input()
for j in range(len(s1)):
if s1[j] == 'X':
A[i][j], d = -1, d + 1
s, d = 0, m * n - d
x, y = map(int, raw_input().split())
k = int(raw_input())
q, dirs = [], []
q.append([x, y, 0])
for i in range(k):
dirs.append(map(int, raw_input().split()))
while q:
x0, y0, p = q.pop(0)
if A[x0][y0] != 0:
continue
A[x0][y0], d = p + 1, d - 1
s = max(A[x0][y0], s)
for k in dirs:
x, y = x0 + k[0], y0 + k[1]
if (0 <= x < n and 0 <= y < m) and A[x][y] == 0:
q.append([x, y, A[x0][y0]])
print s - 1 if d == 0 else -1
发表于 2017-08-27 21:15:40
回复(0)
题目的表述有问题：
1.原点应该是左下角
2.求的是原点到每个可以到达的点的最少步数中最大的一个
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<vector<char>> rec;
struct Position {
int x;
int y;
Position(int x_, int y_) :x(x_), y(y_) {}
bool isOK() {
return 0 <= x && x < N && 0 <= y && y < M && rec[x][y] == '.';
}
Position add(Position p) {
return Position(x + p.x, y + p.y);
}
};
int main() {
while (cin >> N >> M)
{
for (int i = 0; i < N; ++i) {
vector<char> temp(M,0);
for (int j = 0; j < M; ++j)
cin >> temp[j];
rec.push_back(temp);
}
int x0, y0;
cin >> x0 >> y0;
int K;
cin >> K;
vector<Position>pos;
for (int i = 0; i<K; ++i) {
int x, y;
cin >> x >> y;
pos.emplace_back(x, y);
}
Position init(x0, y0);
//
queue<Position> que;
que.push(init);
int step[50][50];
for (int i = 0; i < 50; ++i)
for (int j = 0; j < 50; ++j)
step[i][j]= 100;
step[x0][y0] = 0;
while (!que.empty()) {
auto now = que.front();
que.pop();
for (int i = 0; i < K; ++i) {
auto next = now.add(pos[i]);
if (next.isOK() && step[next.x][next.y]>step[now.x][now.y] + 1) {
step[next.x][next.y] = step[now.x][now.y] + 1;
que.push(next);
}
}
}
int ma=0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
if (rec[i][j] == '.')
ma = max(ma, step[i][j]);
}
}
cout << ((ma == 100) ? -1 : ma) << std::endl;
//
}
return 0;
}
发表于 2017-08-18 15:00:38
回复(0)
#include <iostream>
#include <numeric>
#include <algorithm>
#include <string>
#include <set>
using namespace std;
class point{
public:
int x;
int y;
};
int m,n;
int a[51][51];//地图
int x,y,k;
point p[51];
int fun()
{
int flag;
while(1){
flag=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]!=-1&&a[i][j]!=999999){
for(int l=1;l<=k;l++){
int xx=i+p[l].x;
int yy=j+p[l].y;
if(xx>n||xx<=0||yy>m||yy<=0)continue;
if(a[xx][yy]==-1)continue;
if((a[xx][yy])>(a[i][j]+1)){
a[xx][yy]=a[i][j]+1;
flag=1;
}
}
}
}
}
if(flag==0)
break;
}
//cout<<a[2][3]<<endl;
int res=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==999999)return -1;
if(a[i][j]==-1)continue;
if(res<a[i][j])
res=a[i][j];
}
}
return res;
}
int main()
{
cin>>n>>m;
char c;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>c;
if(c=='.')
a[i][j]=999999;
else
a[i][j]=-1;
}
}
cin>>x>>y>>k;
for(int i=1;i<=k;i++)
cin>>p[i].x>>p[i].y;
a[x+1][y+1]=0;
cout<<fun()<<endl;
return 0;
}
发表于 2017-08-17 10:44:54
回复(0)
BFS，就是代码稍微多一点点。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 52;
char maze[maxn][maxn];
int cnt[maxn][maxn];
int n, m;
int k;
//x0被编译器占用， 所以用x00
int x00, y00;
vector<pair<int, int> > steps;
struct node {
int x, y;
int stepNum;
};
bool ok(int x, int y) {
if(x >= 0 && x < n && y >= 0 && y < m) return true;
return false;
}
int BFS() {
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
//-1代表未访问
cnt[i][j] = -1;
}
}
queue<node> que;
node tmp;
tmp.x = x00;
tmp.y = y00;
tmp.stepNum = 0;
cnt[x00][y00] = 0;
que.push(tmp);
while(!que.empty()) {
node u = que.front();
que.pop();
int newx, newy;
for(int i = 0; i < (int)steps.size(); i++) {
newx = u.x + steps[i].first;
newy = u.y + steps[i].second;
if(!ok(newx, newy)) continue;
//遇到不可以走的地方
else if(maze[newx][newy] == 'X') cnt[newx][newy] = -2;
else {
//说明已经访问过
if(cnt[newx][newy] != -1) continue; ///visited
//没有访问过
else {
cnt[newx][newy] = u.stepNum + 1;
tmp.x = newx;
tmp.y = newy;
tmp.stepNum = u.stepNum + 1;
que.push(tmp);
}
}
}
}
int maxValue = -1;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(maze[i][j] == 'X') continue;
else if(maze[i][j]=='.' && cnt[i][j] == -1) return -1;
maxValue = max(maxValue, cnt[i][j]);
}
}
return maxValue;
}
int main()
{
while(scanf("%d%d", &n, &m) != EOF) {
getchar();
for(int i = 0; i < n; i++) {
scanf("%s", maze[i]);
}
scanf("%d%d", &x00, &y00);
scanf("%d", &k);
pair<int, int> read;
steps.clear();
for(int i = 0; i < k; i++) {
scanf("%d%d", &read.first, &read.second);
steps.push_back(read);
}
int res = BFS();
printf("%d\n", res);
}
return 0;
}
编辑于 2017-08-09 18:53:51
回复(0)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <climits>
#include <algorithm>
#include <queue>
using namespace std;
int n,m,d[55][2];
string g[55];
struct Point
{ int x,y; Point(){} Point(int xx, int yy):x(xx),y(yy){} Point go(int index){ return Point(x+d[index][0], y+d[index][1]); } bool isAvailable(){ return x>=0 && y>=0 && x<n && y<m && g[x][y]=='.'; }
};
int main()
{ int dist[55][55]; int cnt; cin>>n>>m; for(int i=0;i<n;i++) cin>>g[i]; Point s; cin>>s.x>>s.y; cin>>cnt; for(int i=0;i<cnt;i++) cin>>d[i][0]>>d[i][1]; fill(dist[0], dist[54]+55, INT_MAX); dist[s.x][s.y] = 0; queue<Point> q; q.push(s); while(!q.empty()) { Point a = q.front(); q.pop(); for(int i=0;i<cnt;i++) { Point b = a.go(i); if(b.isAvailable()) if(dist[b.x][b.y] > dist[a.x][a.y]+1) { dist[b.x][b.y] = dist[a.x][a.y]+1; q.push(b); } } } int result = 0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(g[i][j]=='.') result = max(result, dist[i][j]); cout<<(result==INT_MAX?-1:result)<<endl; return 0;
}
发表于 2018-02-01 00:50:00
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-08-31 10:18:07 -
2022-08-26 22:18:23 -
2022-08-26 21:49:17
-
2022-08-26 10:36:11
-
2022-08-24 11:19:45
相关试题
-
评论(333) 来自网易2017内推笔试编程...
-
评论(125) 来自网易2017内推笔试编程...
-
评论(204) 来自网易2017内推笔试编程...
-
评论(274) 来自网易2017内推笔试编程...
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
