首页 > 试题广场 >

迷宫寻路

[编程题]迷宫寻路
  • 热度指数:16413 时间限制: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)
求助 超时 通过率40%
发表于 2019-05-31 17:50:34 回复(2)
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)
像求助一下,用的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)
为什么这么多不剪枝的BFS能通过?
难道不会反复横跳吗
发表于 2019-07-27 18:18:28 回复(1)

#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%通过,提示数组越界。
发表于 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)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Point
{
    int x;
    int y;
    int key = 0;//钥匙
};
int X[] = {0,1,0,-1};
int Y[] = {1,0,-1,0};
int main()
{
    int m=0, n=0;
    char input;
    vector<char> row;
    vector<vector<char>> map;
    cin>>m>>n;
    //构建地图
    for(int i=0; i<m; i++)
    {
        row.clear();
        for(int j=0; j<n; j++)
        {
            cin>>input;
            row.push_back(input);
        }
        map.push_back(row);
    }
    //定位出发点与终点
    Point start, end;
    for(int i=0; i<m; i++)
        for(int j=0; j<n; j++)
        {
            if(map[i][j] == '2')
            {
                start.x = i;
                start.y = j;
            }
            else if(map[i][j] == '3')
            {
                end.x = i; 
                end.y = j;
            }
        }
    //开始寻路
    int step = 10000000, key = 0;
    bool ifFind = false;
    char ch;
    Point temp;
    Point add;
    queue<Point> q;
    short value[100][100] = {0};
    q.push(start);
    while(!q.empty())
    {
        temp = q.front();
        q.pop();
        for(int i=0; i<4; i++)
        {
            if(temp.x+X[i]>=0 && temp.y+Y[i]>=0 && temp.x+X[i]<n && temp.y+Y[i]<m)
            {
               
                ch = map[temp.x+X[i]][temp.y+Y[i]];
                switch(ch)
                {
                    case '0':break;
                    case '1'://不是钥匙或者门周围,走过的路就不再走了
                      //  if(value[temp.x+X[i]][temp.y+Y[i]] == 0)
                       // {
                            value[temp.x+X[i]][temp.y+Y[i]] = value[temp.x][temp.y]+1;
                            add.x = temp.x+X[i];
                            add.y = temp.y+Y[i];
                            add.key = temp.key;
                            q.push(add);
                      //  }
                        break;
                    case '2':break;
                    case '3':
                        ifFind = true;
                        value[temp.x+X[i]][temp.y+Y[i]] = value[temp.x][temp.y]+1;
                        if(value[temp.x+X[i]][temp.y+Y[i]]<step)
                            step = value[temp.x+X[i]][temp.y+Y[i]];
                        break;
                    default:
                        if(ch>='a' && ch<='j')//钥匙
                        {
                            key |= 1<<(ch-'a');
                            value[temp.x+X[i]][temp.y+Y[i]] = value[temp.x][temp.y]+1;
                            add.x = temp.x+X[i];
                            add.y = temp.y+Y[i];
                            add.key = key;
                            q.push(add);
                        }
                        if(ch>='A' && ch<='J')//门
                            if(temp.key & (1<<(ch-'A')))//是否有相应的钥匙
                            {
                                value[temp.x+X[i]][temp.y+Y[i]] = value[temp.x][temp.y]+1;
                                add.x = temp.x+X[i];
                                add.y = temp.y+Y[i];
                                add.key ^= 1<<(ch-'A');//消耗钥匙
                                q.push(add);
                            }
                        break;
                }
            }
            if(ifFind)
                break;
        }
        if(ifFind)
            break;
    }
    cout<<step;
    return 0;
}
求大佬帮忙看看,报段错误,但是都有检查,有防止越界的,实在是找不到问题在哪
编辑于 2019-05-09 20:03:10 回复(0)