[编程题]迷宫寻路
- 热度指数：16977 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
- 算法知识视频讲解
假设一个探险家被困在了地底的迷宫之中，要从当前位置开始找到一条通往迷宫出口的路径。迷宫可以用一个二维矩阵组成，有的部分是墙，有的部分是路。迷宫之中有的路上还有门，每扇门都在迷宫的某个地方有与之匹配的钥匙，只有先拿到钥匙才能打开门。请设计一个算法，帮助探险家找到脱困的最短路径。如前所述，迷宫是通过一个二维矩阵表示的，每个元素的值的含义如下 0-墙，1-路，2-探险家的起始位置，3-迷宫的出口，大写字母-门，小写字母-对应大写字母所代表的门的钥匙
输入描述:
迷宫的地图，用二维矩阵表示。第一行是表示矩阵的行数和列数M和N 后面的M行是矩阵的数据，每一行对应与矩阵的一行（中间没有空格）。M和N都不超过100, 门不超过10扇。
输出描述:
路径的长度，是一个整数
示例1
输入
5 5 02111 01a0A 01003 01001 01111
输出
7
层次遍历。有几点需要注意：
1、需要标记已访问节点，注意不是在原图中标记，访问的节点不仅包含坐标，还包含钥匙状态
2、使用int的位来存储钥匙状态，用位运算来判断钥匙，钥匙获得后可重复使用
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct Node {
int x, y, k;
Node(int x, int y, int k) : x(x), y(y), k(k) {}
};
char G[110][110]; // graph
int V[110][110][1100]; // visited
int main() {
int M, N;
cin >> M >> N;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
cin >> G[i][j];
}
}
queue<Node> Q;
int res = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (G[i][j] == '2') {
Q.push(Node(i, j, 0));
while (!Q.empty()) {
int n = Q.size();
res++;
while (n--) {
auto node = Q.front();
Q.pop();
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
for (int d = 0; d < 4; d++) {
int x = node.x + dx[d];
int y = node.y + dy[d];
if (x >= 0 && x < M && y >= 0 && y < N && G[x][y] != '0' && V[x][y][node.k] == 0) {
V[x][y][node.k] = 1;
if (G[x][y] >= 'a' && G[x][y] <= 'z') {
Q.push(Node(x, y, node.k | (1 << (G[x][y] - 'a'))));
} else if (G[x][y] >= 'A' && G[x][y] <= 'Z') {
if (((1 << (G[x][y] - 'A')) & node.k) > 0) {
Q.push(Node(x, y, node.k));
}
} else if (G[x][y] == '3') {
cout << res << endl;
return 0;
} else {
Q.push(Node(x, y, node.k));
}
}
}
}
}
break;
}
}
}
return 0;
}
运行时间：172ms
占用内存：43512k
发表于 2019-03-16 21:13:52
回复(4)
//学习的大家的代码（加注释），没想到用bit位来表示每个门的钥匙状态，规定时间未完成，后附自己的方法，超时了
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Node {
int x;
int y;
int keys;
int deep;
public Node(int x, int y, int keys, int deep) {
super();
this.x = x;
this.y = y;
this.keys = keys;
this.deep = deep;
}
}
public class Main1 {
// maze迷宫，isVisited表示状态是否有过，有过就是true start开始结点
public static int BFS(char[][] maze, boolean[][][] isVisited, Node start) {
Queue<Node> queue = new LinkedList<>(); // bfs队列
queue.add(start);
isVisited[start.x][start.y][0] = true; // 用比特位来表示对应为门是否有要是
// 'A'表示标号为0位的门是否有钥匙
int[][] dirs = new int[][] { { 0, -1 }, { 0, 1 }, { 1, 0 }, { -1, 0 } };
Node now, next; // now 表示当前结点，next表示要进入队列的结点
int M = maze.length;
int N = maze[0].length;
while (!queue.isEmpty()) {
now = queue.poll();
if (maze[now.x][now.y] == '3') { // 如果该点是终点 结束
return now.deep;
}
for (int i = 0; i < 4; i++) {
//当前如果是钥匙，next.keys在下面的步骤会改变
next = new Node(now.x + dirs[i][0], now.y + dirs[i][1], now.keys, now.deep+1);
if (next.x < 0 || next.x >= M || next.y < 0 || next.y >= N
|| maze[next.x][next.y] == '0') { //不能走就不进入队列
continue;
}
if (maze[next.x][next.y] <= 'Z' && maze[next.x][next.y] >= 'A'
&&(now.keys&(1<<(maze[next.x][next.y]-'A')))==0) {
continue; //next结点为门，now没有对应钥匙就不走（next 不进队列）
}
if (maze[next.x][next.y] <= 'z' && maze[next.x][next.y] >= 'a') {
//是钥匙 就将next.keys重新赋值
next.keys=next.keys|1<<(maze[next.x][next.y]- 'a');
}
if (!isVisited[next.x][next.y][now.keys]) {
//next的状态没来过就标记
isVisited[next.x][next.y][now.keys]=true;
//next 进入队列
queue.add(next);
}
}
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String[] strings = sc.nextLine().split(" ");
int M = Integer.valueOf(strings[0]);
int N = Integer.valueOf(strings[1]);
char[][] maze = new char[M][N];
Node start = new Node(0, 0, 0, 0);
int gate=0;
for (int i = 0; i < M; i++) {
maze[i] = sc.nextLine().toCharArray();
for (int j = 0; j < N; j++) {
//找起点
if (maze[i][j] == '2') {
start.x = i;
start.y = j;
}
//统计一共多少门
if (maze[i][j] <= 'Z'&&maze[i][j] >= 'A') {
gate++;
}
}
}
//所有状态的 访问情况
boolean[][][]isVisited=new boolean[M][N][2<<gate];
//只输出路径的步数（不包括起点）
System.out.println(BFS(maze, isVisited, start));
}
sc.close();
}
}
//**************************可以输出路径的代码，但超时************************************** import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
class Node {
int x;
int y;
int keys;
Node pre;
public Node(int x, int y, int keys, Node pre) {
super();
this.x = x;
this.y = y;
this.keys = keys;
this.pre = pre;
}
}
public class Main {
// maze迷宫，isVisited表示状态是否有过，有过就是true start开始结点
public static List<Node> BFS(char[][] maze, boolean[][][] isVisited, Node start) {
List<Node> res = new ArrayList<>(); // 返回结果
Queue<Node> queue = new LinkedList<>(); // bfs队列
Stack<Node> path = new Stack<>(); // 走过的路径
Stack<Node> shortestpath = new Stack<>(); // 最短路径
queue.add(start);
isVisited[start.x][start.y][0] = true; // 用比特位来表示对应为门是否有要是
// 'A'表示标号为0位的门是否有钥匙
int[][] dirs = new int[][] { { 0, -1 }, { 0, 1 }, { 1, 0 }, { -1, 0 } };
Node now, next; // now 表示当前要加入path的结点，next表示要进入队列的结点
int M = maze.length;
int N = maze[0].length;
while (!queue.isEmpty()) {
now = queue.poll();
path.push(now); //bfs 要点出队列的元素要加入路径
if (maze[now.x][now.y] == '3') { // 如果该点是终点 结束
break;
}
for (int i = 0; i < 4; i++) {
//当前如果是钥匙，next.keys在下面的步骤会改变
next = new Node(now.x + dirs[i][0], now.y + dirs[i][1], now.keys, now);
if (next.x < 0 || next.x >= M || next.y < 0 || next.y >= N
|| maze[next.x][next.y] == '0') { //不能走就不进入队列
continue;
}
if (maze[next.x][next.y] <= 'Z' && maze[next.x][next.y] >= 'A'
&&(now.keys&(1<<(maze[next.x][next.y]-'A')))==0) {
continue; //next结点为门，now没有对应钥匙就不走（next 不进队列）
}
if (maze[next.x][next.y] <= 'z' && maze[next.x][next.y] >= 'a') {
//是钥匙 就将next.keys重新赋值
next.keys=next.keys|1<<(maze[next.x][next.y]- 'a');
}
if (!isVisited[next.x][next.y][now.keys]) {
//next的状态没来过就标记
isVisited[next.x][next.y][now.keys]=true;
//next 进入队列
queue.add(next);
}
}
}
//从path中的终点往回溯源，可以得到最短路径
now = path.peek();
while (!path.isEmpty()) {
next = path.pop();
if (now.x == next.x && now.y == next.y) {
shortestpath.add(next);
now = next.pre;
}
}
for (Node node : shortestpath) {
res.add(node);
}
//返回从起点到终点的路径
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String[] strings = sc.nextLine().split(" ");
int M = Integer.valueOf(strings[0]);
int N = Integer.valueOf(strings[1]);
char[][] maze = new char[M][N];
Node start = new Node(0, 0, 0, null);
int gate=0;
for (int i = 0; i < M; i++) {
maze[i] = sc.nextLine().toCharArray();
for (int j = 0; j < N; j++) {
//找起点
if (maze[i][j] == '2') {
start.x = i;
start.y = j;
}
//统计一共多少门
if (maze[i][j] <= 'Z'&&maze[i][j] >= 'A') {
gate++;
}
}
}
//所有状态的 访问情况
boolean[][][]isVisited=new boolean[M][N][2<<gate];
//只输出路径的步数（不包括起点）
System.out.println(BFS(maze, isVisited, start).size()-1);
}
sc.close();
}
}
发表于 2017-08-07 13:52:49
回复(6)
python的bfs超时过不去，不知道有没有大佬有优化的办法。。。
class node:
def __init__(self,x,y,key,step):
self.x=x
self.y=y
self.key=key
self.step=step
m,n=map(int,raw_input().strip().split(' '))
A=[]
for i in range(m):
A.append(list(raw_input()))
ans=0
if not len(A):
print ans
a = 101
b = 101
c = 1025
mp = [0]*101
for i in range(len(mp)):
mp[i] = [0]*101
for i in range(a):
for j in range(b):
mp[i][j] = [0]*c
def bfs(x,y,m,n,A):
queue=[]
queue.append(node(x,y,0,0))
while queue:
nnode=queue.pop(0)
for dx,dy in zip([1,0,-1,0],[0,1,0,-1]):
nx=nnode.x+dx
ny=nnode.y+dy
kkey=nnode.key
if nx<0 or nx>=m or ny<0 or ny>=n or A[nx][ny]=='0':
continue
elif A[nx][ny]=='3':
return nnode.step+1
elif A[nx][ny]>='a' and A[nx][ny]<='z':
kkey=kkey|(1<<(ord(A[nx][ny])-ord('a')))
elif A[nx][ny]>='A' and A[nx][ny]<='Z' and kkey&(1<<(ord(A[nx][ny])-ord('A')))==0:
continue
if mp[nx][ny][kkey]==0:
mp[nx][ny][kkey]=1
queue.append(node(nx,ny,kkey,nnode.step+1))
print -1
for i in range(m):
for j in range(n):
if A[i][j]=='2':
print bfs(i,j,m,n,A)
发表于 2018-05-17 13:30:11
回复(4)
#include <bits/stdc++.h>
using namespace std;
int n, m;
char G[101][101];
bool vis[101][101][1025]={false};
int dir[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
struct P{
int x, y, k, t;
};
int BFS(int sx, int sy){
queue<P> Q;
Q.push({sx, sy, 0, 0});
while(!Q.empty()){
P p = Q.front();
Q.pop();
if(G[p.x][p.y] == '3')
return p.t;
for(int i=0;i<4;i++){
int xx = p.x + dir[i][0];
int yy = p.y + dir[i][1];
int k = p.k, t=p.t;
if(xx>=0 && xx<n && yy>=0 && yy<m && G[xx][yy]!='0'){
if(islower(G[xx][yy]))
k = k | (1<<(G[xx][yy]-'a'));
if(isupper(G[xx][yy]) && (k&(1<<(G[xx][yy]-'A')))==0)
continue;
if(!vis[xx][yy][k]){
vis[xx][yy][k] = true;
Q.push({xx, yy, k, t+1});
}
}
}
}
return 0;
}
int main(){
scanf("%d%d", &n, &m);
for(int i=0;i<n;i++)
scanf("%s", G[i]);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(G[i][j] == '2'){
vis[i][j][0] = true;
printf("%d\n", BFS(i, j));
return 0;
}
return 0;
}
发表于 2020-11-11 01:35:49
回复(0)
import java.util.*;
public class Main{
// 定义一个静态内部类Node,保存到达[row][col]时携带的钥匙串keys和走过的步数steps
static class Node{
static boolean[][][] visit;
int i;
int j;
int keys;
int steps;
public Node(int row, int col, int keys, int steps){
this.i = row;
this.j = col;
this.keys = keys;
this.steps = steps;
if (visit == null){
visit = new boolean[n][m][1024];
}
}
}
static int n;
static int m;
static char[][] map = null;
static int[][] walk = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};// 四个方向移动一步
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while (sc.hasNext()){
// 解析数据
n = sc.nextInt();
m = sc.nextInt();
map = new char[n][m];
for (int i = 0; i < n; i++){
map[i] = sc.next().toCharArray();
}
// 先找到入口，再从入口bfs
Node result = null;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (map[i][j] == '2'){
result = bfs(i, j);
break;
}
}
}
System.out.println(result.steps);
}
}
private static Node bfs(int i, int j){
Queue<Node> queue = new LinkedList<>();
Node start = new Node(i, j, 0, 0);
Node.visit[i][j][0] = true;
queue.add(start);
while (!queue.isEmpty()){
Node node = queue.poll();
for (int t = 0; t < walk.length; t++){
int next_i = node.i + walk[t][0];
int next_j = node.j + walk[t][1];
if (next_i < 0 || next_j < 0 || next_i == n || next_j == m){
continue;
}
char c = map[next_i][next_j];
int keys = node.keys;
int steps = node.steps;
// 到达终点
if (c == '3'){
return (new Node(next_i, next_j, keys, steps + 1));
}
// 碰到门，并且没有对应的钥匙或者碰到墙
if (c >= 'A' && c <= 'Z' && ((keys & (1 << (c - 'A'))) == 0) || c == '0'){
continue;
}
// 碰到钥匙，更新钥匙串
if (c >= 'a' && c <= 'z'){
keys |= (1 << (c - 'a'));
}
// 如果没到过该点，或者回到该点时，身上的钥匙串更新了
if (!Node.visit[next_i][next_j][keys]){
Node.visit[next_i][next_j][keys] = true;
queue.add(new Node(next_i, next_j, keys, steps + 1));
}
}
}
return null;
}
}
发表于 2019-06-11 13:31:25
回复(0)
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class pdd4 {
public static void main(String args[]) {
Scanner scan = new Scanner(System.in);
int m = scan.nextInt();
int n = scan.nextInt();
scan.nextLine();
char A[][] = new char[m][n];
for (int i = 0; i < m; ++i) {
String s = scan.nextLine();
for (int j = 0; j < n; ++j) {
A[i][j] = s.charAt(j);
}
}
System.out.println(maze(A));
}
/**
* 0 2 1 1 1
* 0 1 a 0 A
* 0 1 0 0 3
* 0 1 0 0 1
* 0 1 1 1 1
*
* @param A
* @return
*/
public static int maze(char A[][]) {
int i = 0, j = 0;
for (i = 0; i < A.length; ++i)
for (j = 0; j < A[0].length; ++j)
if (A[i][j] == '2')
return bfs(A, i, j);
return -1;
}
public static int bfs(char A[][], int i, int j) {
int m = A.length, n = A[0].length;
boolean visit[][][] = new boolean[m][n][1200];
Queue<node> queue = new LinkedList<>();
int direction[][] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};//左右上下
node p = new node(i, j, 0, 0);
visit[i][j][0] = true;
queue.add(p);
while (!queue.isEmpty()) {
node q = queue.poll();
if (A[q.x][q.y] == '3')
return q.level;
for (i = 0; i < 4; ++i) {
p = new node(q.x + direction[i][0], q.y + direction[i][1], q.keys, q.level + 1);
if (p.x < 0 || p.x >= m || p.y < 0 || p.y >= n || A[p.x][p.y] == '0') {
continue;
}
//遇见门且没钥匙
if (A[p.x][p.y] >= 'A' && A[p.x][p.y] <= 'Z' && ((1 << (A[p.x][p.y] - 'A')) & q.keys) == 0) {
continue;
}
if (A[p.x][p.y] >= 'a' && A[p.x][p.y] <= 'z') {
p.keys = q.keys | (1 << (A[p.x][p.y] - 'a'));
}
if (!visit[p.x][p.y][p.keys]) {
visit[p.x][p.y][p.keys] = true;
queue.add(p);
}
}
}
return -1;
}
}
class node {
int x;
int y;
int keys;
int level;
public node(int i, int j, int k, int l) {
x = i;
y = j;
keys = k;
level = l;
}
}
</node>
发表于 2019-01-15 22:23:46
回复(1)
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
int offset[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
int book[100][100][1024] = {0};
struct node{ int x, y, key, step; node(int x, int y, int key, int step):x(x), y(y), key(key), step(step){}
};
int bfs(vector<string> maze, int x, int y)
{ queue<node> Q; Q.push(node(x, y, 0, 0)); while (!Q.empty()) { node h = Q.front(); Q.pop(); if(maze[h.y][h.x] == '3') return h.step; for (int i = 0; i < 4; i++) { int nx = h.x + offset[i][0], ny = h.y + offset[i][1]; if(nx < 0 || nx >= maze[0].size() || ny < 0 || ny >= maze.size() || maze[ny][nx] == '0') continue; int keyState = h.key; if(maze[ny][nx] >= 'a' && maze[ny][nx] <= 'z') keyState |= (1 << (maze[ny][nx] - 'a'));//捡钥匙 if(maze[ny][nx] >= 'A' && maze[ny][nx] <= 'Z' && (keyState & (1 << (maze[ny][nx] - 'A'))) == 0) continue; //没有打开门的钥匙 if(!book[ny][nx][keyState]) { book[ny][nx][keyState] = 1; Q.push(node(nx, ny, keyState, h.step + 1)); } } } return 0;
}
int main()
{
int m, n;
vector<string> mp;//存储迷宫
cin >> m >> n;
while(m--)
{
string s;
cin >> s;
mp.push_back(s);
} int flag = 0;
for(int j = 0; j < mp.size(); j++)
{
for(int i = 0; i < n; i++)
{
if(mp[j][i] == '2') { flag = 1; book[j][i][0] = 1; cout << bfs(mp, i, j) << endl; break; }
} if(1 == flag) break;
}
return 0;
}
发表于 2019-03-08 22:03:58
回复(0)
//AC代码:
#include<stdio.h>
#include<queue>
#include<string.h>
#include<vector>
using namespace std;
char G[105][105];
int book[105][105][1200],N,M;
int Next[4][2]={0,1,0,-1,1,0,-1,0};
int bfs(int,int);
struct node{
int x,y,k,step;
node(int x,int y,int k,int step):x(x),y(y),k(k),step(step){}
};
int main(){
int i,j;
//freopen("input.txt","r",stdin);
while(scanf("%d%d",&N,&M)!=EOF){
for(i=0;i<N;i++) scanf("%s",G[i]);
memset(book,0,sizeof(book));
int flag=0;
for(i=0;i<N;i++){
if(flag==1) break;
for(j=0;j<M;j++)
if(G[i][j]=='2'){
flag=1;
book[i][j][0]=1;
printf("%d\n",bfs(i,j));
break;
}
}
}
}
int bfs(int startX,int startY){
queue<node> Q;
Q.push(node(startX,startY,0,0));
while(!Q.empty()){
node head=Q.front();Q.pop();
if(G[head.x][head.y]=='3') return head.step;
for(int i=0;i<4;i++){
int nx=head.x+Next[i][0],ny=head.y+Next[i][1];
if(nx>=N||nx<0||ny>=M||ny<0||G[nx][ny]=='0') continue;
int key=head.k;
if('a'<=G[nx][ny]&&G[nx][ny]<='z') key=key|(1<<(G[nx][ny]-'a'));
if('A'<=G[nx][ny]&&G[nx][ny]<='Z'&&(key&(1<<(G[nx][ny]-'A')))==0) continue;
if(!book[nx][ny][key]){
book[nx][ny][key]=1;
Q.push(node(nx,ny,key,head.step+1));
}
}
}
return 0;
}//这题就是普通的bfs多了‘钥匙’这个状态
//所以book[x][y][key]的意义就是 横坐标为x,纵坐标为y,钥匙状态为key的点是否访问过
//钥匙的状态 就用二进制数表示 最多10 把钥匙 那就是1024
//比如我现在有第二把钥匙和第四把钥匙 那么我的钥匙状态就是 0101000000 也就是 320
编辑于 2017-08-06 11:23:31
回复(37)
import java.util.*;
public class Main {
static class Node{
int x;
int y;
int key;
int step;
public Node(int x,int y,int key,int step){
this.x=x;
this.y=y;
this.key=key;
this.step=step;
}
}
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int N=in.nextInt();
int M=in.nextInt();
in.nextLine();
char[][] G=new char[N][M];
for(int i=0;i<N;i++){
G[i]=in.nextLine().toCharArray();
}
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
if(G[i][j]=='2'){
System.out.println(bfs(i,j,N,M,G));
return;
}
}
}
}
private static int bfs(int si, int sj,int N,int M,char[][] G) {
Queue<Node> queue=new LinkedList<>();
int[][][] mp=new int[101][101][1025];
int[][] next={{-1,0},{0,-1},{1,0},{0,1}};
queue.offer(new Node(si,sj,0,0));
while(!queue.isEmpty()){
Node node=queue.poll();
for(int i=0;i<4;i++){
int x=node.x+next[i][0];
int y=node.y+next[i][1];
int key=node.key;
if(x<0||x>=N||y<0||y>=M||G[x][y]=='0') continue;
else if(G[x][y]=='3') return node.step+1;
else if(G[x][y]<='z'&&G[x][y]>='a') key=key|(1<<(G[x][y]-'a'));
else if(G[x][y]<='Z'&&G[x][y]>='A'&&(key&(1<<(G[x][y]-'A')))==0) continue;
if(mp[x][y][key]==0){
mp[x][y][key]=1;
queue.offer(new Node(x,y,key,node.step+1));
}
}
}
return -1;
}
}
编辑于 2017-08-07 01:17:32
回复(9)
import java.util.*;
// 使用带有计数的层序遍历，求得最短根叶长度
// 带有附加钥匙限制的情况下，用更高维的数组记录是否访问过
// 该题实际字母字符不会超过j
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int m = sc.nextInt(), n = sc.nextInt();
char[][] maze = new char[m][n];
sc.nextLine();
for(int i = 0; i < m; i++) maze[i] = sc.nextLine().toCharArray();
sc.close();
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
if(maze[i][j] == '2') {System.out.println(solution(maze,i,j)); return;}
}
private static int solution(char[][] maze, int startX, int startY){
int res = 0;
int m = maze.length, n = maze[0].length;
boolean[][][] isVisted = new boolean[m][n][1024];
isVisted[startX][startY][0] = true;
int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
Queue<Integer> queue = new LinkedList<>();
queue.offer(startX); queue.offer(startY); queue.offer(0);
while(!queue.isEmpty()){
int num = queue.size()/3; // 带有计数的层序遍历
res++; // 层数
while(num > 0){
startX = queue.poll(); startY = queue.poll(); int k = queue.poll();
num--;
for(int i = 0; i < 4; i++){
int x = startX + dir[i][0]; int y = startY + dir[i][1]; int key = k;
if(x<0 || x>=m || y<0 || y>=n || maze[x][y] == '0') continue;
else if(maze[x][y] == '3') return res;
else if(maze[x][y] <= 'j' && maze[x][y] >= 'a') key = key | 1 << maze[x][y]-'a';
else if(maze[x][y] <= 'J' && maze[x][y] >= 'A' && (key & 1 << maze[x][y]-'A') == 0) continue;
if(isVisted[x][y][key] == false){ // 注意不能加else 也不能加 == '1'，否则缺少小写字符的情况
isVisted[x][y][key] = true;
queue.offer(x); queue.offer(y); queue.offer(key);
}
}
}
}
return -1;
}
}
发表于 2019-02-13 16:53:07
回复(3)
#python，求助，只通过30%
import sys
size=sys.stdin.readline().strip().split()
m, n = int(size[0]), int(size[1])
maze=[[0]*n for i in range(m)]
for i in range(m):
line=sys.stdin.readline().strip()
maze[i]=list(line)
#钥匙的状态 就用二进制数表示 最多10 把钥匙 那就是1024
class Node:
def __init__(self, x, y, key, step):
self.x=x
self.y=y
self.key=key #key的状态用二进制表示
self.step=step
def bfs(si,sj,m,n,maze):
from queue import Queue
q=Queue()
mp=[[[0]*1025 for i in range(101)] for j in range(101)]
nex=[[-1,0],[0,-1],[1,0],[0,1]]
q.put(Node(si,sj,0,0))
while not q.empty():
node=q.get()
for i in range(4):
x=node.x+nex[i][0]
y=node.y+nex[i][1]
key=node.key
if x<0 or x>=m or y<0 or y>=n or maze[x][y]=='0':
continue
elif maze[x][y]=='3':
return node.step+1
elif 'a'<=maze[x][y]<='z':
key=key | (1<<(ord(maze[x][y])-ord('a')))
elif 'A'<=maze[x][y]<='Z' and (key & (1<<(ord(maze[x][y])-ord('A'))))==0:
continue
if mp[x][y][key]==0:
mp[x][y][key]=1
q.put(Node(x,y,key,node.step+1))
return None
if __name__ == '__main__':
for i in range(m):
for j in range(n):
if maze[i][j]=='2':
print(bfs(i,j,m,n,maze))
发表于 2019-03-19 13:21:24
回复(5)
#include <bits/stdc++.h>
using namespace std;
//搜索节点，节点包含位置x,y,捡到的钥匙的状态,当前步数
struct Node
{
int x, y, key, step;
Node(int x, int y, int key, int step) :x(x), y(y), key(key), step(step) {}
};
int nextDirection[4][2] = { 0,1,0,-1,1,0,-1,0 }; //搜索的四个方向
char G[105][105]; //地图的布局
//第三维为当前钥匙的状态
//用二进制位表示当前的钥匙状态，如0000000001，表示1有号门的钥匙，
//由题意最多只有10个门，故最大状态位1111111111，其10进制值位1024，故设置位1200>1024
int mark[105][105][1200];
int m,n;
//宽度优先搜索，用到队列，队列保存搜索的节点
int bfs(int startX, int startY)
{
//宽度优先搜索队列
queue<Node> Q;
Q.push(Node(startX,startY,0,0)); //将出发点加入队列
while(!Q.empty())
{
//弹出队列的第一个元素，进行一轮搜索
Node head=Q.front(); Q.pop();
//如果该节点为终点，返回最短路径的长度(出口)
if(G[head.x][head.y]=='3') return head.step;
//如果不为终点，从该节点四个方向依次搜索，当搜索的节点满足下面的条件，就将该轮搜索的所有节点加到队列中
for(int i=0;i<4;i++)
{
//搜索朝某个方向移动
int newX=head.x + nextDirection[i][0];
int newY=head.y + nextDirection[i][1];
//如果移动后的位置越界或者为墙壁（0），跳出当前循环，搜索另一个方向
if(newX>=m || newX<0 || newY>=n ||newY<0 || G[newX][newY]=='0' ) continue;
//当非越界非墙壁，判断是门还是钥匙
int k=head.key;
//如果移动的位置是钥匙，更新钥匙的状态
//这里用到了位运算：与|和移位操作
if('a'<=G[newX][newY] && G[newX][newY]<='z') k = k | (1<<(G[newX][newY]-'a'));
//如果移动的位置是门，判断钥匙的状态能否开门，无法开门跳出本次循环并搜索下一个方向
if('A'<=G[newX][newY] && G[newX][newY]<='Z' && (k &(1<<(G[newX][newY]-'A')))== 0) continue;
//如果移动的位置为道路（1）或者是门但钥匙能打开，判断该位置是否已经到达过，未到达则标记为已到达并将当前节点加入队列
if(!mark[newX][newY][k])
{
mark[newX][newY][k]=1;
Q.push(Node(newX,newY,k,head.step+1));
}
}
}
}
int main()
{
//输入
scanf("%d%d", &m, &n);
for (int i = 0; i<m; i++)
{
scanf("%s", G[i]);
}
memset(mark, 0, sizeof(mark));
//先遍历找起始点
bool flag = true;
for (int i = 0; i<m && flag; i++)
{
for (int j = 0; j<n; j++)
{
if (G[i][j] == '2')
{
flag = false;
mark[i][j][0] = 1;
printf("%d\n", bfs(i, j));
break;
}
}
}
return 0;
}
编辑于 2019-07-27 22:05:22
回复(0)
import java.util.*;
class Node {
int x, y, keys, steps;
public Node(int x, int y, int keys, int steps) {
this.x = x;
this.y = y;
this.keys = keys;
this.steps = steps;
}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static int m, n;
public static char[][] maze;
public static int[][][] visited; //保存是否已经计算过
public static int[] dirX = {0, 0, 1, -1};
public static int[] dirY = {1, -1, 0, 0};
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
m = in.nextInt();
n = in.nextInt();
in.nextLine();
maze = new char[m][n];
visited = new int[m][n][1024];
for (int i = 0; i < m; i++) {
String str = in.nextLine();
//in.nextLine();
maze[i] = str.toCharArray();
//System.out.println(maze[i]);
}
int ans = -1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (maze[i][j] == '2') {
visited[i][j][0] = 1;
ans = bfs(i, j);
break;
}
}
}
System.out.println(ans);
}
public static int bfs(int i, int j) {
Queue<Node> q = new LinkedList<>();
//将入口加入队列，没钥匙，0步
q.add(new Node(i, j, 0, 0));
while (!q.isEmpty()) {
Node node = q.poll();
//下面特别注意当前点是node.x,node.y，不是i,j
if (maze[node.x][node.y] == '3') {
//到达出口，退出
return node.steps;
}
//4个方向扩散
for (int d = 0; d < 4; d++) {
int newX = node.x + dirX[d];
int newY = node.y + dirY[d];
if (newX >= 0 && newX < m && newY >= 0 && newY < n) {
int key = node.keys;
if (maze[newX][newY] == '0') {
continue;
}
//遇到钥匙，增加新钥匙
if (maze[newX][newY] >= 'a' && maze[newX][newY] <= 'z') {
key = key | (1 << (maze[newX][newY] - 'a'));
}
//遇到门，且当前钥匙串没有对应钥匙，结束
if (maze[newX][newY] >= 'A' && maze[newX][newY] <= 'Z'
&& (key & (1 << (maze[newX][newY] - 'A'))) == 0) {
continue;
}
//剩下是可通过情形
if (visited[newX][newY][key] == 0) {
visited[newX][newY][key] = 1;
q.add(new Node(newX, newY, key, node.steps + 1));
}
}
}
}
return 0;
}
}
发表于 2025-01-21 21:02:30
回复(0)
像求助一下，用的A*写的，可是居然会超时。我怎么觉得比bfs算法复杂度低呢？
# 读取输入数据 [M,N]= list(map(int,input().split())) maxz = [] for x in range(M): maxz.append(list(input())) # ------------------------------------------------- # M=5 # N=5 # maxz=[['0','2','1','1','1'], # ['0','1','a','0','A'], # ['0','1','0','0','3'], # ['0','1','0','0','1'], # ['0','1','1','1','1']] # ------------------------------------------------- # 数据初始化 start0 = [] end0 = [] # 提取所有带字母的钥匙和门 dicta = [] dictb = [] for x in range(M): for y in range(N): if maxz[x][y] == '2': start0 = [x, y] elif maxz[x][y] == '3': end0 = [x, y] elif 96 < ord(maxz[x][y]) < 123&nbs***bsp;64 < ord(maxz[x][y]) < 91: dicta.append([maxz[x][y], x, y]) # 按钥匙字母排序 dicta.sort(key=lambda x: x[0]) lena = len(dicta) # 转换成钥匙和门的组合 for x in range(lena // 2): dictb.append(dicta[(lena // 2) + x][1:3]) dictb.append(dicta[x][1:3]) # --------------------------------------------------------- # 计算 G,H,F,P值 G为当前点到起点的距离，H为当前点到终点的距离，F为G+H，P为来源点 def distance(Node_current7, yuandian, start8, end8): P = yuandian G = abs(Node_current7[0] - start8[0]) + abs(Node_current7[1] - start8[1]) H = abs(Node_current7[0] - end8[0]) + abs(Node_current7[1] - end8[1]) F = G + H return [F, P] # 查找周围的临接点 def findNeighbors(nc, maxz9, Node_start7, Node_end7): open_list9 = [] if nc[0] > 0: # 取上面的点 if maxz9[nc[0] - 1][nc[1]] != '0': open_list9.append([nc[0] - 1, nc[1], distance([nc[0] - 1, nc[1]], nc[0:2], Node_start7, Node_end7)]) if nc[0] < M - 1: # 取下面的点 if maxz9[nc[0] + 1][nc[1]] != '0': open_list9.append([nc[0] + 1, nc[1], distance([nc[0] + 1, nc[1]], nc[0:2], Node_start7, Node_end7)]) if nc[1] > 0: # 取左面的点 if maxz9[nc[0]][nc[1] - 1] != '0': open_list9.append([nc[0], nc[1] - 1, distance([nc[0], nc[1] - 1], nc[0:2], Node_start7, Node_end7)]) if nc[1] < (N - 1): # 取右面的点 if maxz9[nc[0]][nc[1] + 1] != '0': open_list9.append([nc[0], nc[1] + 1, distance([nc[0], nc[1] + 1], nc[0:2], Node_start7, Node_end7)]) return open_list9 # 从openlist找到F值最小 def findMinNode(openlist_temp): y1 = openlist_temp[0] for x1 in openlist_temp: if y1[2][0] > x1[2][0]: y1 = x1 return y1 # A*搜索 def aStarSearch(Node_start, Node_end, maxz0): OpenList = [] CloseList = [] Node_current = [] List_neighbors = [] term_result = [] # 把起点加入 open list OpenList.append([Node_start[0], Node_start[1], [0, [-1, -1]]]) # 主循环，每一轮检查一个当前方格节点 while len(OpenList) > 0: # 在OpenList中查找 F值最小的节点作为当前方格节点 Node_current = findMinNode(OpenList) # 当前方格节点从open list中移除 OpenList.remove(Node_current) # 当前方格节点进入 close list CloseList.append(Node_current) # 找到所有邻近节点 List_neighbors = findNeighbors(Node_current, maxz0, Node_start, Node_end) for x in List_neighbors: if (x not in OpenList) & (x not in CloseList): # 邻近节点不在OpenList,CloseList中，标记父亲、G、H、F，并放入OpenList OpenList.append(x) # 如果终点在OpenList中，直接返回路径 for x in OpenList: if Node_end == x[0:2]: # 如果找到 term_result.append(x[0:2]) temp0 = x while Node_start != temp0[0:2]: for z in CloseList: if temp0[2][1] == z[0:2]: temp0 = z term_result.append(temp0[0:2]) break term_result.pop() # print(term_result[::-1]) return len(term_result) # OpenList用尽，仍然找不到终点，说明终点不可到达，返回空 return None #逐个遍历各个位置，从起点 到第一个钥匙，然后再到第一个门，如果有其他钥匙，再循环，最后去出口。循环计算两点间的距离。 dictb.insert(0, start0) dictb.append(end0) sum0 = 0 for y in range(len(dictb) - 1): sum0 += aStarSearch(dictb[y], dictb[y + 1], maxz) print(sum0)
发表于 2020-02-09 15:57:26
回复(0)
#include <bits/stdc++.h>
using namespace std;
int x[4] = {0,0,1,-1};
int y[4] = {1,-1,0,0};
int min_path = INT_MAX;
int m,n;
void dfs(char** maze, int path, int i, int j, int key, bool*** visit)
{
if(path>=min_path) return;//剪枝
if(i<0||i>=m||j<0||j>=n||maze[i][j]=='0'||visit[i][j][key]) return;//无效
if(maze[i][j]>='a'&&maze[i][j]<='z')
{
key = key | (1<<(maze[i][j]-'a'));//获得钥匙,更新状态
}
else if(maze[i][j]>='A'&&maze[i][j]<='Z'&&((key&(1<<(maze[i][j]-'A')))==0))
{
return;
}//无钥匙过不了门
else if(maze[i][j]=='3')
{
min_path = min(min_path, path);
return;
}//到终点
visit[i][j][key] = true;
for(int k=0;k<4;k++)
{
int nexti = i + x[k];
int nextj = j + y[k];
dfs(maze, path+1, nexti, nextj, key, visit);
}
visit[i][j][key] = false;
}
int main()
{
cin>>m>>n;
// vector<vector<char>> maze(m, vector<char>(n));
char** maze = new char*[m];
bool*** visit = new bool**[m];
// visit.assign(m, vector<vector<bool>>(n,vector<bool>(1024,false)));
int sx,sy;
for(int i=0;i<m;i++)
{
visit[i] = new bool*[n];
maze[i] = new char[n];
for(int j=0;j<n;j++)
{
visit[i][j] = new bool[1024];
cin>>maze[i][j];
if(maze[i][j]=='2')
{
sx = i;
sy = j;
}
}
}
dfs(maze, 0, sx, sy,0,visit);
cout<<min_path<<endl;
}
只过了30%，然后超时，求大神解答。。。
发表于 2019-07-29 01:25:58
回复(0)
#include <bits/stdc++.h>
using namespace std;
bool vis[1024][101][101];
int n,m;
char mp[102][102];
int sx,sy;
struct node
{
int x,y;
int status;
int dis;
node(){}
node(int xx,int yy,int status,int dis):x(xx),y(yy),status(status),dis(dis) {}
};
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
queue<node> q;
int main(int argc, char const *argv[]){
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>mp[i]+1;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(mp[i][j]=='2'){
sx=i,sy=j;
goto loop;
}
loop:;
node p;
vis[0][sx][sy]=1;
q.push(node(sx,sy,0,0));
while(!q.empty()) {
p=q.front();
q.pop();
// printf("%d %d %d %d\n\n",p.status,p.x,p.y,p.dis );
// vis[p.status][p.x][p.y]=1;
if(mp[p.x][p.y]=='3'){
cout<<p.dis<<endl;
break;
}
for(int i=0;i<4;++i) {
int xx=p.x+dx[i],yy=p.y+dy[i];
if(xx<=0||xx>n||yy<=0||yy>m||mp[xx][yy]=='0'||vis[p.status][xx][yy]) continue;
if(mp[xx][yy]>='A'&&mp[xx][yy]<='Z') {
if(p.status&(1<<(mp[xx][yy]-'A'))) {
vis[p.status][xx][yy]=1;
q.push(node(xx,yy,p.status,p.dis+1));
}
}
else if(mp[xx][yy]>='a'&&mp[xx][yy]<='z') {
vis[p.status|(1<<(mp[xx][yy]-'a'))][xx][yy]=1;
q.push(node(xx,yy,p.status|(1<<(mp[xx][yy]-'a')),p.dis+1));
}
else{
vis[p.status][xx][yy]=1;
q.push(node(xx,yy,p.status,p.dis+1));
}
}
}
return 0;
}
发表于 2019-06-23 16:18:28
回复(0)
m,n = list(map(int, input().split()))
roads = [] #存储地图
route_stack = []
book = [[[0 for z in range(1024)] for x in range(52)] for y in range(52)]
# 读入数据，找到起始位置
for i in range(m):
tmp = list(input())
roads.append(tmp)
if "2" in tmp:
sx, sy = i, tmp.index("2")
route_stack.append([sx,sy,0,0]) # 坐标x,y，存储钥匙，步数step,
step = 0
# 可以移动的位子，分别对应右左上下
dxs = [1, -1, 0, 0]
dys = [0, 0, 1, -1]
i = 0 # 标记点位置
# bfs广度搜索
# bfs广度搜索
while route_stack: # 不为空则可以继续
head = route_stack.pop(0)
if roads[head[0]][head[1]] == '3':
print(head[3])
break
#开始走路
for dx,dy in zip(dxs,dys):
key = head[2]
nx = head[0] + dx
ny = head[1] + dy
if nx < 0 or nx >= m or ny < 0 or ny >= n or roads[nx][ny] == '0':
continue
if "a" <= roads[nx][ny] <= "z":
key = head[2]|(1<<(ord(roads[nx][ny])-ord('a')))
if ('A'<=roads[nx][ny] and roads[nx][ny]<='Z') and (key&(1<<(ord(roads[nx][ny])-ord('A'))))==0:
continue
if not book[nx][ny][key] :
book[nx][ny][key]=1
route_stack.append([nx,ny,key,head[3]+1])
求助，按着@元气の悟空的思路用python写的，30%通过，提示数组越界。
roads = [] #存储地图
route_stack = []
book = [[[0 for z in range(1024)] for x in range(52)] for y in range(52)]
# 读入数据，找到起始位置
for i in range(m):
tmp = list(input())
roads.append(tmp)
if "2" in tmp:
sx, sy = i, tmp.index("2")
route_stack.append([sx,sy,0,0]) # 坐标x,y，存储钥匙，步数step,
step = 0
# 可以移动的位子，分别对应右左上下
dxs = [1, -1, 0, 0]
dys = [0, 0, 1, -1]
i = 0 # 标记点位置
# bfs广度搜索
# bfs广度搜索
while route_stack: # 不为空则可以继续
head = route_stack.pop(0)
if roads[head[0]][head[1]] == '3':
print(head[3])
break
#开始走路
for dx,dy in zip(dxs,dys):
key = head[2]
nx = head[0] + dx
ny = head[1] + dy
if nx < 0 or nx >= m or ny < 0 or ny >= n or roads[nx][ny] == '0':
continue
if "a" <= roads[nx][ny] <= "z":
key = head[2]|(1<<(ord(roads[nx][ny])-ord('a')))
if ('A'<=roads[nx][ny] and roads[nx][ny]<='Z') and (key&(1<<(ord(roads[nx][ny])-ord('A'))))==0:
continue
if not book[nx][ny][key] :
book[nx][ny][key]=1
route_stack.append([nx,ny,key,head[3]+1])
求助，按着@元气の悟空的思路用python写的，30%通过，提示数组越界。
发表于 2019-06-12 11:12:59
回复(0)
import java.util.*;
public class Main{
public static void main(String[] arg){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int m=sc.nextInt();
char[][] A=new char[n][m];
int[] start=new int[2];
int[] end=new int[2];
int[][] dir=new int[][]{{0,-1},{-1,0},{1,0},{0,1}};
for(int i=0;i<n;i++){
String row=sc.next();
for(int j=0;j<m;j++){
A[i][j]=row.charAt(j);
if(A[i][j]=='2'){
start[0]=i;
start[1]=j;
}else if(A[i][j]=='3'){
end[0]=i;
end[1]=j;
}
}
}
boolean[][][] visited=new boolean[n][m][1<<10];
LinkedList<int[]> queue=new LinkedList<>();
queue.add(new int[]{start[0],start[1],0});
visited[start[0]][start[1]][0]=true;
int cnt=0;
out:
while(queue.size()>0){
cnt++;
int len=queue.size();
while(len-->0){
int[] q=queue.poll();
int x=q[0],y=q[1],keys=q[2];
for(int i=0;i<4;i++){
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(nx==end[0]&&ny==end[1]) break out;
int nkeys=keys;
if(nx<0||nx>=n||ny<0||ny>=m||A[nx][ny]=='0') continue;
//int r=0;
if('a'<=A[nx][ny]&&A[nx][ny]<='z'){
int key=A[nx][ny]-'a';
nkeys=(1<<key)|nkeys;
}else if('A'<=A[nx][ny]&&A[nx][ny]<='Z'){
int key=A[nx][ny]-'A';
if(((nkeys>>key)&1)==0) continue;
}
if(visited[nx][ny][nkeys]) continue;
visited[nx][ny][nkeys]=true;
queue.add(new int[]{nx,ny,nkeys});
}
}
}
System.out.println(cnt);
}
}
}
编辑于 2019-06-06 03:07:17
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-14 12:59:29
-
2023-03-11 20:40:09
-
2023-03-08 09:02:17
-
2022-09-08 11:58:37
-
2022-09-07 23:39:21
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
