57
//AC代码:
#include
#include
#include
#include
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
memset(book,0,sizeof(book));
int flag=0;
for(i=0;i
if(flag==1) break;
for(j=0;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 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<
if('A'<=G[nx][ny]&&G[nx][ny]<='Z'&&(key&(1<
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
回复(36)
13
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
G[i]=in.nextLine().toCharArray();
}
for(int i=0;i
for(int j=0;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 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<
else if(G[x][y]<='Z'&&G[x][y]>='A'&&(key&(1<
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
回复(8)
8
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 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)
3
层次遍历。有几点需要注意：
1、需要标记已访问节点，注意不是在原图中标记，访问的节点不仅包含坐标，还包含钥匙状态
2、使用int的位来存储钥匙状态，用位运算来判断钥匙，钥匙获得后可重复使用
#include
#include
#include
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 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)
2
//学习的大家的代码(加注释)，没想到用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 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<
continue; //next结点为门，now没有对应钥匙就不走(next 不进队列)
}
if (maze[next.x][next.y] <= 'z' && maze[next.x][next.y] >= 'a') {
//是钥匙 就将next.keys重新赋值
next.keys=next.keys|1<
}
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<
//只输出路径的步数(不包括起点)
System.out.println(BFS(maze, isVisited, start));
}
sc.close();
}
}
/
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 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;
}
}
发表于 2019-01-15 22:23:46
回复(1)
1
#include
#include
#include
#include
#include
#include
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 maze, int x, int y)
{ queue 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 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)
像求助一下，用的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
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]
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]
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
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<
}
else if(maze[i][j]>='A'&&maze[i][j]<='Z'&&((key&(1<
{
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> maze(m, vector(n));
char** maze = new char*[m];
bool*** visit = new bool**[m];
// visit.assign(m, vector>(n,vector(1024,false)));
int sx,sy;
for(int i=0;i
{
visit[i] = new bool*[n];
maze[i] = new char[n];
for(int j=0;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<
} 只过了30%，然后超时，求大神解答。。。
发表于 2019-07-29 01:25:58
回复(0)
为什么这么多不剪枝的BFS能通过？
难道不会反复横跳吗
发表于 2019-07-27 18:18:28
回复(1)
#include
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 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<
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<
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<
q.push(node(xx,yy,p.status|(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<
if ('A'<=roads[nx][ny] and roads[nx][ny]<='Z') and (key&(1<
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
String row=sc.next();
for(int j=0;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 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<
}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
#include
#include
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 row;
vector> map;
cin>>m>>n;
//构建地图
for(int i=0; i
{
row.clear();
for(int j=0; j
{
cin>>input;
row.push_back(input);
}
map.push_back(row);
}
//定位出发点与终点
Point start, end;
for(int i=0; i
for(int j=0; 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 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]
{
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 = value[temp.x+X[i]][temp.y+Y[i]];
break;
default:
if(ch>='a' && ch<='j')//钥匙
{
key |= 1<
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<
{
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<
q.push(add);
}
break;
}
}
if(ifFind)
break;
}
if(ifFind)
break;
}
cout<
return 0;
} 求大佬帮忙看看，报段错误，但是都有检查，有防止越界的，实在是找不到问题在哪
编辑于 2019-05-09 20:03:10
回复(0)
![python迷宫寻路_PTA-迷宫寻路（输出最短路径）[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)