定义一个二维数组 N*M ，如 5 × 5 数组下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。
数据范围： ， 输入的内容只包含
[编程题]迷宫问题
- 热度指数：210777 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
输入两个整数，分别表示二维数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
输出描述:
左上角到右下角的最短路径，格式如样例所示。
示例1
输入
5 5 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
输出
(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4)
示例2
输入
5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0
输出
(0,0) (1,0) (2,0) (3,0) (4,0) (4,1) (4,2) (4,3) (4,4)
说明
注意：不能斜着走！！
while True:
try:
m,n = map(int,input().split())
matrix = []
for i in range(m):
d = list(map(int,input().split()))
#print(c)
matrix.append(d)
def dfs(path):
if path[-1] == [m-1,n-1]:
return path
r, c = path[-1]
matrix[r][c] = 2
directions = [[r+1,c],[r,c+1],[r-1,c],[r,c-1]]
for i,j in directions:
if 0<=i<m and 0<=j<n and matrix[i][j]==0:
final_path = dfs(path+[[i,j]])
if final_path[-1] == [m-1,n-1]:
return final_path
return path#很重要，保证输出
path = dfs([[0,0]])
for i in path:
print('({},{})'.format(i[0],i[1]))
except:
break
try:
m,n = map(int,input().split())
matrix = []
for i in range(m):
d = list(map(int,input().split()))
#print(c)
matrix.append(d)
def dfs(path):
if path[-1] == [m-1,n-1]:
return path
r, c = path[-1]
matrix[r][c] = 2
directions = [[r+1,c],[r,c+1],[r-1,c],[r,c-1]]
for i,j in directions:
if 0<=i<m and 0<=j<n and matrix[i][j]==0:
final_path = dfs(path+[[i,j]])
if final_path[-1] == [m-1,n-1]:
return final_path
return path#很重要，保证输出
path = dfs([[0,0]])
for i in path:
print('({},{})'.format(i[0],i[1]))
except:
break
发表于 2022-01-10 12:16:36
回复(0)
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
var flag=true,m,n,arr=[],res
function findWay(i,j,direction,path){
if(i==m-1 && j==n-1){
for(let i in path){
console.log('('+path[i][0]+','+path[i][1]+')')
}
}
if(i+1<m && arr[i+1][j]==0 && direction[1]!=0){
findWay(i+1,j,[0,1,1,1],path.concat([[i+1,j]]))
}
if(i-1>=0 && arr[i-1][j]==0 && direction[0]!=0){
findWay(i-1,j,[1,0,1,1],path.concat([[i-1,j]]))
}
if(j+1<n && arr[i][j+1]==0 && direction[3]!=0){
findWay(i,j+1,[1,1,0,1],path.concat([[i,j+1]]))
}
if(j-1>=0 && arr[i][j-1]==0 && direction[2]!=0){
findWay(i,j-1,[1,1,1,0],path.concat([[i,j-1]]))
}
}
rl.on('line', function (line) {
const tokens = line.split(' ');
if (tokens[tokens.length-1]=='') tokens.pop()
if(flag){
m=parseInt(tokens[0]),n=parseInt(tokens[1])
flag=false
}
else{
arr.push(tokens.map((value,index,arr)=>{
return parseInt(value)
}))
if(arr.length==m){
//console.log(arr)
findWay(0,0,[0,1,0,1],[[0,0]])
arr=[]
flag=true
}
}
});
js递归
发表于 2021-09-27 19:12:36
回复(0)
感觉像小游戏一样，每到分岔路口存个档，撞墙了就回档，把错路全部标记为墙，档坏了回上一个档，直至终点。
题目确定仅有一条通路，也挺方便的
# include <iostream>
# include <vector>
using namespace std;
int main(){
int m, n;
vector<pair<int, int>> step = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
while(cin >> m >> n){
vector<vector<int>> mapp(m+2, vector<int>(n+2, 1)); // 地图
vector<pair<int, int>> path = {{1, 1}}; // 记录路径
vector<pair<int, int>> save = {{1, 1}}; // 记录节点
for(int i=1; i<=m; i++){
for (int j=1; j<=n; j++) cin >> mapp[i][j];
}
mapp[1][1] = 1;
while (path.back()!=make_pair(m, n)) {
int wall = 0;
pair<int, int> chc;
for (int i=0; i<4; i++){
int xn = path.back().first + step[i].first;
int yn = path.back().second + step[i].second;
if (mapp[xn][yn]==1) wall++;
else {chc = make_pair(xn, yn);}
}
if (wall==4) {
// 走过的地方全是墙，回退的时候会将死胡同标记为墙
if (path.back() == save.back()) save.pop_back();
while (path.back() != save.back()) path.pop_back();
}else if (wall==3){
path.push_back(chc);
mapp[chc.first][chc.second] = 1;
}else {
save.push_back(path.back());
path.push_back(chc);
mapp[chc.first][chc.second] = 1;
}
}
for (int i=0; i<path.size(); i++)
cout << '(' << path[i].first-1 << ',' << path[i].second-1 << ')' << endl;
}
return 0;
}
发表于 2021-08-31 17:19:38
回复(0)
//回溯
import java.util.*;
public class Main{
private static List<int[]> ans = new ArrayList<>();
private static List<int[]> path = new ArrayList<>();
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
int m = sc.nextInt();
int[][] maze = new int[n][m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
maze[i][j] = sc.nextInt();
}
}
//深度优先搜索
dfs(maze, 0, 0);
for(int[] arr : ans){
System.out.println("("+arr[0]+","+arr[1]+")");
}
//清空路径path，结果集ans，实际ans指向新建对象，无需清空
path.clear();ans.clear();
}
}
private static void dfs(int[][] maze, int i, int j){
//结束条件，一定要用路径新建集合，path最后会remove为空
if(i==maze.length-1 && j==maze[0].length-1){
path.add(new int[]{i, j});
ans = new ArrayList<>(path);
return;
}
//边界条件，剪枝
if(i<0 || i>=maze.length || j<0 || j>=maze[0].length || maze[i][j]==1) return;
//i,j加入集合,并且当前位置设置为障碍
path.add(new int[]{i, j});
maze[i][j]=1;
//向四个方向递归
dfs(maze, i+1, j);
dfs(maze, i, j+1);
dfs(maze, i-1, j);
dfs(maze, i, j-1);
//找到死胡同，回溯，撤销i,j选择，当前位置设置为可走
path.remove(path.size()-1);
maze[i][j]=0;
}
}
发表于 2021-08-06 10:13:36
回复(2)
import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
bfs搜索，然后打印路径即可--- 不想递归打印的，可以从从右下往左上搜索
/*
public class Main{
static int n, N = 12, m;
static int[][] g = new int[N][N];
static boolean[][] st = new boolean[N][N];
static int[][] dis = new int[][]{ {1, 0}, {-1, 0}, {0, -1}, {0, 1} };
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()){
n = in.nextInt(); m = in.nextInt();
for(int i = 0; i < n; i ++)
for(int j = 0; j < m; j ++){
g[i][j] = in.nextInt();
}
for(int i = 0; i < n; i ++)
Arrays.fill(st[i], false);
bfs();
}
}
static void bfs(){
st[0][0] = true;
Queue<Node> queue = new LinkedList<>();
Node start = new Node(0, 0);
queue.add(start);
while(!queue.isEmpty()){
Node t = queue.poll();
int a = t.x, b = t.y;
for(int[] d : dis){
int x = a + d[0], y = d[1] + b;
if(x < 0 || x >= n || y < 0 || y >= m || g[x][y] == 1 || st[x][y]) continue;
st[x][y] = true;
Node tmp = new Node(x, y);
tmp.next = t;
if(x == n - 1 && y == m - 1){
//找到
print(tmp);
return;
}
queue.add(tmp);
}
}
}
static void print(Node root){
if(root == null) return;
print(root.next);
System.out.println("(" + root.x + "," + root.y + ")");
}
static class Node{
int x, y;
Node next;
public Node(int x, int y){
this.x = x;
this.y = y;
}
}
}
发表于 2021-08-03 14:01:25
回复(0)
从起点开始不断四个方向探索，直到走到出口，走的过程中我们借助栈记录走过路径的坐标，栈记录
坐标有两方面的作用，一方面是记录走过的路径，一方面方便走到死路时进行回溯找其他的通路。
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef struct Position
{
int row;
int col;
}Pos;
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//栈创建
typedef Pos STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}Stack;
void StackInit(Stack* ps)
{
assert(ps);
ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (ps->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
ps->capacity = 4;
ps->top = 0;//初始给0，top指向栈顶元素的下一个；
}
void StackDestory(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
//入栈
void StackPush(Stack* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
ps->a = tmp;
ps->capacity *= 2;
}
}
ps->a[ps->top] = x;
ps->top++;
}
//出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);//栈空了，直接终止报错
ps->top--;
}
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);//栈空了，直接终止报错
return ps->a[ps->top - 1];
}
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//迷宫主程序
Stack path;
//判断是否有通路
bool IsPass(int** Maze, int N, int M, Pos next)
{
if (next.col >= 0 && next.col < M && next.row >= 0 && next.row < N && Maze[next.row][next.col] == 0)
return true;
else
return false;
}
//判断是否有到终点的路
bool GetMazePath(int** Maze, int N, int M, Pos cur)
{
StackPush(&path, cur);
//判断是否到出口
if (cur.col == M - 1 && cur.row == N - 1)
return true;
Pos next;
//将走过的地方置2，防止重走
Maze[cur.row][cur.col] = 2;
//探测上下左右四个方向
//上
next = cur;
next.row -= 1;
if (IsPass(Maze, N, M, next))
{
//如果有通路将继续递归
if (GetMazePath(Maze, N, M, next))
return true;
}
//下
next = cur;
next.row += 1;
if (IsPass(Maze, N, M, next))
{
if (GetMazePath(Maze, N, M, next))
return true;
}
//左
next = cur;
next.col -= 1;
if (IsPass(Maze, N, M, next))
{
if (GetMazePath(Maze, N, M, next))
return true;
}
//右
next = cur;
next.col += 1;
if (IsPass(Maze, N, M, next))
{
if (GetMazePath(Maze, N, M, next))
return true;
}
//当走到思路，将走错的坐标删除
StackPop(&path);
return false;
}
//采用栈储存路径
//由于先进后出，栈顶为出口，栈底为入口，需要反过来
//所以再创建一个栈将数据倒过来再输出
void PrintPath(Stack path)
{
Stack rPath;
StackInit(&rPath);
while (!StackEmpty(&path))
{
StackPush(&rPath, StackTop(&path));
StackPop(&path);
}
while (!StackEmpty(&rPath))
{
Pos top = StackTop(&rPath);
printf("(%d,%d)\n", top.row, top.col);
StackPop(&rPath);
}
StackDestory(&rPath);
}
int main()
{
int N = 0, M = 0;
while (scanf("%d%d", &N, &M) != EOF)
{
//创建迷宫
//先创建行坐标
//由于是二位数组，先创建一个含有N个数组指针的指针数组，指针数组储存的是指针，所以指向这个指针数组的指针为二级指针
//指针数组中每个指针都为数组指针，每个数组指针指向的数组为每一行
int** Maze = (int**)malloc(sizeof(int*) * N);
for (int i = 0; i < N; i++)
{
//Maze[i]就是int*，是一个指针，开辟的空间储存int
Maze[i] = (int*)malloc(sizeof(int) * M);
}
//输入迷宫
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
scanf("%d", &Maze[i][j]);
}
}
//初始化栈
StackInit(&path);
//定起点
Pos entry = { 0,0 };
if (GetMazePath(Maze, N, M, entry))
{
PrintPath(path);
}
else
{
printf("没有找到通路\n");
}
StackDestory(&path);
for (int i = 0; i < N; i++)
{
free(Maze[i]);
}
free(Maze);
Maze = NULL;
}
return 0;
}
发表于 2021-07-12 00:29:00
回复(0)
import sys
def print_result(path):
for item in path:
print('({},{})'.format(item[0], item[1]))
def min_path(maze, visited, path, m, n, i, j):
if i >= m&nbs***bsp;j >= n&nbs***bsp;i < 0&nbs***bsp;j < 0:
return
if visited[i][j]:
return
if maze[i][j] == 1:
return
if i == m-1 and j == n-1 and maze[i][j] == 0:
path.append((i, j))
print_result(path)
return
path.append((i, j))
visited[i][j] = True
min_path(maze, visited, path, m, n, i+1, j)
min_path(maze, visited, path, m, n, i-1, j)
min_path(maze, visited, path, m, n, i, j+1)
min_path(maze, visited, path, m, n, i, j-1)
path.pop()
visited[i][j] = False
def get_input():
m, n = list(map(int, input().strip().split()))
maze = []
for i in range(m):
row = list(map(int, input().strip().split()))
maze.append(row)
return maze, m, n
if __name__ == '__main__':
try:
while True:
maze, m, n = get_input()
row = [False for _ in range(n)]
visited = [row.copy() for _ in range(m)]
path = []
min_path(maze, visited, path, m, n, 0, 0)
except Exception:
pass
发表于 2021-07-11 11:25:09
回复(0)
#include<iostream>
#include<stdio.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int main()
{
int row,col;
while(cin>>row>>col) {
vector<vector<int>> dst(row,vector<int>(col,-1)); //dst[i][j]记录是从哪个格子到达的(i,j)
vector<vector<int>> arr(row,vector<int>(col,0));
for(int i=0;i<row;++i) {
for(int j=0;j<col;++j)
cin>>arr[i][j];
}
queue<pair<int,int>> q;
dst[0][0]=0;
q.push(pair<int,int>(0,0));
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
bool flag=false;
while(!q.empty()) {
auto [x,y]=q.front(); q.pop();
for(int i=0;i<4;++i) {
int newx=x+dx[i];
int newy=y+dy[i];
if(newx>=0 && newx<row && newy>=0 && newy<col && arr[newx][newy]==0 && dst[newx][newy]==-1) {
dst[newx][newy]=x*100+y;
if(newx==row-1 && newy==col-1) {
flag=true;
break;
}
q.push(pair<int,int>(newx,newy));
}
}
if(flag)
break;
}
int from=dst[row-1][col-1];
vector<string> res;
while(from!=0) {
int x=from/100;
int y=from%100;
res.push_back("("+to_string(x)+","+to_string(y)+")");
from=dst[x][y];
}
cout<<"(0,0)"<<endl;
for(int i=res.size()-1;i>=0;i--) {
cout<<res[i]<<endl;
}
cout<<"("<<(row-1)<<","<<(col-1)<<")"<<endl;
}
return 0;
}
发表于 2021-06-27 19:52:04
回复(0)
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
import java.util.regex.Pattern;
import java.util.regex.Matcher;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()) {
int row = in.nextInt();
int col = in.nextInt();
int[][] maze = new int[row][col];
for (int i=0; i<row; i++)
for (int j=0; j<col; j++)
maze[i][j] = in.nextInt();
recursion(maze, 0, 0, -1);
ArrayList<Point> list = new ArrayList();
int x = row - 1, y = col - 1;
int n = maze[x][y];
// 从右下角根据步数，开始搜索最优路径（唯一），循环放入list
while (true) {
// 因为从后面开始循环，所以每次放入第一位
list.add(0,new Point(x, y));
// 步数时负数，所以++
n ++;
// 为0，则表示到达左上角
if (n == 0)
break;
// 目的： 找出与n相同的步数
if (x - 1 >= 0 && maze[x - 1][y] == n){
x -= 1;
continue;
}
if (x + 1 < row && maze[x + 1][y] == n){
x += 1;
continue;
}
if (y - 1 >= 0 && maze[x][y - 1] == n){
y -= 1;
continue;
}
if (y + 1 < col && maze[x][y + 1] == n){
y += 1;
continue;
}
}
for (Point p : list)
System.out.println("(" + p.r + "," + p.c + ")");
}
}
// 深度优先搜索 （递归）
// 思路 : 0 位可以走， 1 为墙， 递归时，传入走的步数 （这里从-1 开始递减）
public static void recursion(int[][] maze, int r, int y, int i) {
// 如果为墙， 或者当前位已经走过，且走的步数（负数） <= 当前位的步数 ，直接返回
if (maze[r][y] == 1 || (maze[r][y] < 0 && maze[r][y] >= i))
return;
// 这里可以直接更新步数
maze[r][y] = i;
// 判断是否到达右下角
if (r == maze.length - 1 && y == maze[0].length - 1)
return;
// 往上走
if (r - 1 >= 0)
recursion(maze, r - 1, y, i - 1);
// 往下走
if (r + 1 < maze.length)
recursion(maze, r + 1, y, i - 1);
// 往左走
if (y - 1 >= 0)
recursion(maze, r, y - 1, i - 1);
// 往右走
if (y + 1 < maze[0].length)
recursion(maze, r, y + 1, i - 1);
}
}
// 定义一个用来保存坐标的类
class Point {
int r;
int c;
Point(int r, int c) {
this.r = r;
this.c = c;
}
}
发表于 2021-02-02 11:19:17
回复(0)
题目要求：路径唯一，则不是寻找最优路径，而是寻找唯一路径且数据规模不大，dfs递归+栈即可，递归地入栈从而得到所需答案。ps：走地图类题目常用技巧：1、使用step数组来决定方向和步数，2、在地图外围一圈防止越界，最后输出坐标均减一即可。
#include<iostream>
#include<stack>
using namespace std;
int step[4][2] = {
0, 1,
1, 0,
0, -1,
-1, 0
};
struct Pos {
int x, y;
};
stack<Pos> s;
int map[15][15];
bool check(int x, int y, int n, int m) {
if(map[x][y] == 1) return false;
if(x == n && y == m) {
s.push({x, y});
return true;
}
for(int i = 0; i < 4; i++) {
if(check(x + step[i][0], y + step[i][1], n, m)) {
s.push({x, y});
return true;
}
}
return false;
}
int main() {
int n, m;
while(cin >> n >> m) {
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> map[i][j];
for(int i = 0; i <= n; i++) {
map[i][0] = map[i][m + 1] = 1;
}
for(int i = 0; i <= m; i++) {
map[0][i] = map[n + 1][i] = 1;
}
check(1, 1, n, m);
while(!s.empty()) {
cout << "(" << s.top().x - 1 << "," << s.top().y - 1 << ")" << endl;
s.pop();
}
}
return 0;
}
编辑于 2021-01-28 21:22:53
回复(0)
import java.util.*;
// HJ43
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int n = in.nextInt();
int m = in.nextInt();
int[][] map = new int[n][m];
for (int i = 0; i < n * m; i++) {
int num = in.nextInt();
map[i / m][i % m] = num;
}
Point start = new Point(0, 0, m), end = new Point(m - 1, n - 1, m);
LinkedList<Point> result = compute(n, m, map, start, end);
if (Objects.isNull(result)) {
System.out.println("ERROR");
continue;
}
result.forEach(System.out::println);
}
}
private static LinkedList<Point> compute(int rowNum, int colNum, int[][] map, Point start, Point end) {
// 构造邻接矩阵
int pointNum = rowNum * colNum;
int[][] lin = new int[pointNum][pointNum];
Map<Integer, Point> repo = new HashMap<>(pointNum);
repo.put(start.toIndex(), start);
repo.put(end.toIndex(), end);
for (int i = 0; i < pointNum; i++) {
int x = i % colNum;
int y = i / colNum;
int pointType = map[y][x];
repo.putIfAbsent(i, new Point(x, y, colNum));
for (int j = 0; j < 9; j++) {
int tx = x - 1 + (j % 3);
int ty = y - 1 + (j / 3);
if (tx < 0 || ty < 0 || tx >= colNum || ty >= rowNum) {
continue;
}
int targetIndex = toIndex(tx, ty, colNum);
if (i == targetIndex || lin[i][targetIndex] > 0) {
continue;
}
if (j == 0 || j == 2 || j == 4 || j == 6 || j == 8) {
continue;
}
switch (pointType) {
case 1:
lin[i][targetIndex] = 1;
lin[targetIndex][i] = 1;
break;
case 0:
if (map[ty][tx] == 1) {
lin[i][targetIndex] = 1;
lin[targetIndex][i] = 1;
} else {
lin[i][targetIndex] = 2;
lin[targetIndex][i] = 2;
}
break;
}
}
}
// 查询数量
return computeAvailable(lin, repo, start, end, rowNum, colNum);
}
private static LinkedList<Point> computeAvailable(int[][] lin, Map<Integer, Point> repo, Point p1, Point p2, int rowNum, int colNum) {
p1.passed = true;
if (lin[p1.toIndex()][p2.toIndex()] == 2) {
p1.passed = false;
return new LinkedList<>(Arrays.asList(p1, p2));
}
boolean available = false;
LinkedList<Point> minSubList = new LinkedList<>();
for (int i = 0; i < 9; i++) {
int tx = p1.x - 1 + (i % 3);
int ty = p1.y - 1 + (i / 3);
if (tx < 0 || ty < 0 || tx >= colNum || ty >= rowNum) {
continue;
}
int targetIndex = toIndex(tx, ty, colNum);
Point targetPoint = repo.get(targetIndex);
if (!targetPoint.passed && lin[p1.toIndex()][targetPoint.toIndex()] == 2) {
LinkedList<Point> subList = computeAvailable(lin, repo, targetPoint, p2, rowNum, colNum);
if (Objects.nonNull(subList) && subList.size() < (minSubList.isEmpty() ? repo.size() : minSubList.size())) {
minSubList = subList;
available = true;
}
}
}
p1.passed = false;
if (available) {
minSubList.addFirst(p1);
return minSubList;
}
return null;
}
private static int toIndex(int x, int y, int colNum) {
return y * colNum + x;
}
private static class Point {
final int x;
final int y;
final int colNum;
boolean passed = false;
public Point(int x, int y, int colNum) {
this.x = x;
this.y = y;
this.colNum = colNum;
}
public int toIndex() {
return y * colNum + x;
}
@Override
public String toString() {
return "(" + y +
"," + x +
')'
;
}
}
}
发表于 2020-11-11 03:45:51
回复(0)
def trace(start, end, maps):
# 获取坐标
m, n = len(maps), len(maps[0])
x, y = start[0], start[1]
# 判断能否走
if x < 0&nbs***bsp;y < 0&nbs***bsp;x > m - 1&nbs***bsp;y > n - 1: return
if maps[x][y] == 1: return
# 走过的路改为 1，添加到路径
maps[x][y] = 1
stack.append(start)
# 判断是否到达终点
if start == end:
if best_path == []&nbs***bsp;len(stack) < len(best_path):
best_path.clear()
for p in stack:
best_path.append(p)
# 这里防止到达终点后继续走下一步，不加也行，只是迭代步数更多
stack.pop()
maps[x][y] = 0
return
# 向四个方向走
trace([x - 1, y], end, maps)
trace([x + 1, y], end, maps)
trace([x, y - 1], end, maps)
trace([x, y + 1], end, maps)
# 还原，删除路径
stack.pop()
maps[x][y] = 0
while True:
try:
MAP = []
stack = []
best_path = []
M, N = map(int, input().split())
for point in range(M):
MAP.append(list(map(int, input().split())))
trace([0, 0], [M - 1, N - 1], MAP)
for point in best_path:
print('(%d,%d)' % (point[0], point[1]))
except:
break
编辑于 2020-09-17 17:56:55
回复(0)
import java.util.*;
public class Main{
//存储所有的路径和路径长度
static Map<LinkedList<String>, Integer> res = new HashMap<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int m = sc.nextInt();
int n = sc.nextInt();
int[][] arr = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] = sc.nextInt();
}
}
res.clear();
LinkedList<String> trace = new LinkedList<>();
int x = 0;
int y = 0;
dfs(arr, 0, 0, 1, trace);
int min = Integer.MAX_VALUE;
LinkedList<String> minTrace = new LinkedList<>();
for(Map.Entry<LinkedList<String>, Integer> t : res.entrySet()){
if(t.getValue() < min){
min = t.getValue();
minTrace = t.getKey();
}
}
for(int i=0; i<minTrace.size(); i++){
System.out.println(minTrace.get(i));
}
}
}
public static void dfs(int[][] arr, int x, int y, int cnt, LinkedList<String> trace){
int m = arr.length;
int n = arr[0].length;
if(x == m-1 && y == n-1){
trace.add("(" + x + "," + y +")");
res.put(new LinkedList<>(trace), cnt);
return;
}
if(x >= m || y >= n || arr[x][y] == 1 ){
return;
}
//添加当前节点为trace
trace.add("(" + x + "," + y +")");
dfs(arr, x+1, y,cnt+1, trace);
dfs(arr, x, y+1, cnt+1, trace);
trace.removeLast();
}
}
发表于 2020-08-23 21:56:54
回复(0)
import java.util.Scanner;
public class Main{
private static int a,b;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
a = sc.nextInt();
b = sc.nextInt();
int[][] matrix = new int[a][b];
for(int i=0;i<a;i++){
for(int j=0;j<b;j++){
matrix[i][j]=sc.nextInt();
}
}
getRoute(matrix,0,0);
}
sc.close();
}
public static boolean getRoute(int[][] matrix,int i,int j){
if(i==(a-1) && j==(b-1)){
System.out.println( "(" + i + "," + j +")" );
return true;
}
if(matrix[i][j]==0){
matrix[i][j]=1;
System.out.println( "(" + i + "," + j +")" );
if(i<a && j<(b-1) && getRoute(matrix,i,j+1))
return true;
else if(i<(a-1) && j<b && getRoute(matrix,i+1,j))
return true;
else return false;
}else{
return false;
}
}
}
public class Main{
private static int a,b;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
a = sc.nextInt();
b = sc.nextInt();
int[][] matrix = new int[a][b];
for(int i=0;i<a;i++){
for(int j=0;j<b;j++){
matrix[i][j]=sc.nextInt();
}
}
getRoute(matrix,0,0);
}
sc.close();
}
public static boolean getRoute(int[][] matrix,int i,int j){
if(i==(a-1) && j==(b-1)){
System.out.println( "(" + i + "," + j +")" );
return true;
}
if(matrix[i][j]==0){
matrix[i][j]=1;
System.out.println( "(" + i + "," + j +")" );
if(i<a && j<(b-1) && getRoute(matrix,i,j+1))
return true;
else if(i<(a-1) && j<b && getRoute(matrix,i+1,j))
return true;
else return false;
}else{
return false;
}
}
}
发表于 2020-08-05 11:40:17
回复(0)
Java BFS, 妈蛋中间出了些小bug找了我半个小时。。。。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int row = sc.nextInt();
int col = sc.nextInt();
int[][] maze = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
maze[i][j] = sc.nextInt();
}
}
Main main = new Main();
bfs(maze);
}
sc.close();
}
public static void bfs(int[][] maze) {
Queue<Point> q = new LinkedList<>();
List<List<Point>> map = new ArrayList<>();
int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
boolean[][] visited = new boolean[maze.length][maze[0].length];
for (int i = 0; i < maze.length; i++) {
Arrays.fill(visited[i], Boolean.FALSE);
map.add(new ArrayList<Point>());
for (int j = 0; j < maze[0].length; j++) {
map.get(i).add(new Point(i, j));
}
}
visited[0][0] = true;
q.offer(map.get(0).get(0));
loop: while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
Point curr = q.poll();
for (int[] dir : dirs) {
int xx = curr.getX() + dir[0], yy = curr.getY() + dir[1];
//迷宫范围内 可以通过 之前没走过
if (xx >= 0 && xx < maze.length && yy >= 0 && yy < maze[0].length && maze[xx][yy] == 0 && !visited[xx][yy]) {
visited[xx][yy] = true;
Point p = map.get(xx).get(yy);
p.setPrev(curr);
q.offer(p);
if (xx == maze.length - 1 && yy == maze[0].length - 1) {
break loop;
}
}
}
}
}
//从终点反推找回起点
List<Point> path = new ArrayList<>();
Point curr = map.get(maze.length - 1).get(maze[0].length - 1);
while (curr != null) {
path.add(curr);
curr = curr.getPrev();
}
for (int i = path.size() - 1; i >= 0; i--) {
System.out.println("(" + path.get(i).getX() + "," + path.get(i).getY() + ")");
}
}
}
class Point {
private int x, y, len;
private Point prev;
public Point(int x, int y) {
this.x = x;
this.y = y;
prev = null;
}
public int getX(){
return x;
}
public int getY(){
return y;
}
public void setPrev(Point p) {
prev = p;
}
public Point getPrev() {
return prev;
}
}
发表于 2020-07-19 16:51:09
回复(0)
深度优先遍历搜索。
从（0,0）开始整个矩阵矩阵，只能向上向下，向左向右走，且前方没有障碍物并且没有走过。遍历过程需要记录下来当前点是从哪个点（如果为点（i，j）存储对于id: i*m+j）走过来的。当遍历到（n,m）时，可以得到一条最短路径。然后从（n,m）倒序恢复整条路径。
import java.util.*;
public class Main {
static int[] dx, dy;
static int[][] bfs(int[][] grid, int n, int m) {
//id : x*m + y
int[][] ans = new int[n][m];
Queue<Integer> q = new LinkedList<>();
q.offer(0);
while(!q.isEmpty()) {
int cur = q.poll();
int x = cur / m, y = cur % m;
//System.out.println(x+","+y);
for(int j=0; j < 4; j++) {
int xx = dx[j] + x, yy = dy[j] + y;
if(xx>= 0 && xx<n && yy >=0 && yy < m && grid[xx][yy] == 0) {
grid[xx][yy] = 2;
q.offer(xx*m+yy);
ans[xx][yy] = cur;
}
}
}
//System.out.println(Arrays.deepToString(ans));
return ans;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
dx = new int[] {0, 1, 0, -1};
dy = new int[] {1, 0, -1, 0};
while(sc.hasNext()){
int n =sc.nextInt(), m = sc.nextInt();
int[][] grid = new int[n][m];
for(int i=0; i < n; i++)
for(int j=0; j < m; j++)
grid[i][j] = sc.nextInt();
int[][] path = bfs(grid, n, m);
List<int[]> res = new ArrayList<>();
res.add(new int[] {n-1, m-1});
int x = n-1, y = m-1;
while(!(x == 0 && y == 0)) {
int t = path[x][y];
x = t / m; y = t % m;
res.add(new int[] {x, y});
}
for(int i=res.size()-1; i >= 0; i--) {
System.out.println("(" + res.get(i)[0] +"," + res.get(i)[1]+")");
}
}
}
}
发表于 2020-07-09 12:30:23
回复(0)
本题可用回溯法求解 具体步骤为：
1. 首先将当前点加入路径，并设置为已走
2. 判断当前点是否为出口，是则输出路径，保存结果；跳转到4
3. 依次判断当前点的上、下、左、右四个点是否可走，如果可走则递归走该点
4. 当前点推出路径，设置为可走
#include <iostream>
#include <vector>
using namespace std;
int m, n;//分别代表行和列
vector<vector<int>> maze;//迷宫矩阵
vector<vector<int>> path_temp;//存储当前路径，第一维表示位置
vector<vector<int>> path_best;//存储最佳路径
void MazeTrack(int i, int j){
maze[i][j] = 1;//标记当前节点已走，不可再走
path_temp.push_back({i, j});//将当前节点加入到路径中
if(i == m - 1 && j == n - 1){//判断是否到达终点
if(path_best.empty() || path_temp.size() < path_best.size()){
path_best = path_temp;
}
}
if(i - 1 >= 0 && maze[i - 1][j] == 0){//探索向上走是否可行
MazeTrack(i - 1, j);
}
if(i + 1 < m && maze[i + 1][j] == 0){//探索向下走是否可行
MazeTrack(i + 1, j);
}
if(j - 1 >= 0 && maze[i][j - 1] == 0){//探索向左走是否可行
MazeTrack(i, j - 1);
}
if(j + 1 < n && maze[i][j + 1] == 0){//探索向右走是否可行
MazeTrack(i, j + 1);
}
maze[i][j] = 0;//恢复现场，设为未走
path_temp.pop_back();
}
int main(){
while(cin >> m >> n){
maze = vector<vector<int>>(m, vector<int>(n, 0));
path_temp.clear();
path_best.clear();
for(auto& i : maze){
for(auto& j : i){
cin >> j;
}
}
MazeTrack(0, 0);//回溯寻找迷宫的最短路径
for(auto& i : path_best){
cout << '(' << i[0] << ',' << i[1] << ')' << endl;//输出通路
}
}
return 0;
} 另一种方式遍历（简单一点）： #include <iostream>
#include <vector>
using namespace std;
int m, n;//分别代表行和列
vector<vector<int>> maze;//迷宫矩阵
vector<vector<int>> path_temp;//存储当前路径，第一维表示位置
vector<vector<int>> path_best;//存储最佳路径
int _nextPosition[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
void MazeTrack(int x, int y){
maze[x][y] = 1;//标记当前节点已走，不可再走
path_temp.push_back({x, y});//将当前节点加入到路径中
if(x == m - 1 && y == n - 1){//判断是否到达终点
if(path_best.empty() || path_temp.size() < path_best.size()){//最小路径
path_best = path_temp;
return;
}
}
for(int k = 0; k < 4; ++k){
int nx = x + _nextPosition[k][0];
int ny = y + _nextPosition[k][1];
//如果位置越界或者是1，则跳过
if(nx < 0 || nx >= m || ny < 0 || ny >= n || maze[nx][ny] == 1){
continue;
}
MazeTrack(nx, ny);
}
maze[x][y] = 0;//恢复现场，设为未走
path_temp.pop_back();
}0
int main(){
while(cin >> m >> n){
maze = vector<vector<int>>(m, vector<int>(n, 0));
path_temp.clear();
path_best.clear();
for(auto& i : maze){
for(auto& j : i){
cin >> j;
}
}
MazeTrack(0, 0);//回溯寻找迷宫的最短路径
for(auto& i : path_best){
cout << '(' << i[0] << ',' << i[1] << ')' << endl;//输出通路
}
}
return 0;
}
编辑于 2020-06-26 17:35:37
回复(0)
考虑前后左右情况的java解法
import java.util.Scanner;
import java.util.ArrayList;
public class Main{
public static ArrayList<String>list=new ArrayList<>();
public static ArrayList<String>best=new ArrayList<>();
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
list.clear();
best.clear();
int h=sc.nextInt();
int l=sc.nextInt();
int arr[][]=new int[h][l];
for(int i=0;i<h;i++){
for(int j=0;j<l;j++){
arr[i][j]=sc.nextInt();
}
}
MazeTrack(arr,0,0);
// System.out.println(best.toString());
for(int i=0;i<best.size();i++){
System.out.println(best.get(i));
}
}
}
public static void MazeTrack(int[][]arr, int x, int y){
list.add("("+x+","+y+")");
//System.out.println(list.toString());
arr[x][y]=1;
int h=arr.length;
//System.out.println(h);
int l=arr[0].length;
// System.out.println(l);
if(x==h-1&&y==l-1){
if(best.size()==0||list.size()<best.size()) {
best.clear();
for(int i=0;i<list.size();i++)
best.add(list.get(i));
}
//System.out.println(best);
}
if(x-1>=0&&arr[x-1][y]==0){
MazeTrack(arr,x-1,y);
}
if(y-1>=0&&arr[x][y-1]==0){
MazeTrack(arr,x,y-1);
}
if(x+1<h&&arr[x+1][y]==0){
MazeTrack(arr,x+1,y);
}
if(y+1<l&&arr[x][y+1]==0){
MazeTrack(arr,x,y+1);
}
arr[x][y]=0;
list.remove("("+x+","+y+")");
//System.out.println(best);
}
}
发表于 2020-05-05 20:24:30
回复(0)
#include<iostream>
#include<vector>
using namespace std;
void MiGong(vector<vector<int> > matrix, vector<int>& res, vector<int>& vec_temp,int row, int col){
vec_temp.push_back(row);
vec_temp.push_back(col);
matrix[row][col]=1;
if(row==matrix.size()-1&&col==matrix[0].size()-1){
if(res.empty() || vec_temp.size()<res.size()){
res.clear();
res.insert(res.begin(),vec_temp.begin(),vec_temp.end());
}
}
else {
// 往下走
if (row + 1 <= matrix.size() - 1 && matrix[row + 1][col] == 0) {
MiGong(matrix, res, vec_temp, row + 1, col);
vec_temp.pop_back();
vec_temp.pop_back();
matrix[row + 1][col] = 0;
}
// 往上走
if (row - 1 >= 0 && matrix[row - 1][col] == 0) {
MiGong(matrix, res, vec_temp, row - 1, col);
vec_temp.pop_back();
vec_temp.pop_back();
matrix[row - 1][col] = 0;
}
// 往右走
if (col + 1 <= matrix[0].size() - 1 && matrix[row][col + 1] == 0) {
MiGong(matrix, res, vec_temp, row, col + 1);
vec_temp.pop_back();
vec_temp.pop_back();
matrix[row][col + 1] = 0;
}
// 往左走
if (col - 1 >= 0 && matrix[row][col - 1] == 0) {
MiGong(matrix, res, vec_temp, row, col - 1);
vec_temp.pop_back();
vec_temp.pop_back();
matrix[row][col - 1] = 0;
}
}
}
int main(){
int n,m;
while(cin>>n>>m){
int temp;
vector<vector<int> > matrix(n,vector<int>(m,0));
vector<int> res;
vector<int> vec_temp;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin>>temp;
matrix[i][j]=temp;
}
}
MiGong(matrix, res, vec_temp,0, 0);
for(int i=0; i<res.size(); i++){
cout<<'('<<res[i]<<','<<res[i+1]<<')'<<endl;
i++;
}
}
return 0;
}
编辑于 2020-03-22 23:11:56
回复(0)
//这题使用的是bfs，这里有几个你不能错过的广搜的技巧：
//1 构造队列记录路径
//2 先将周围一圈都设置为已经访问过，这样不用判断是否会越界
//3 移动的方向不用写8个int,直接int dir[5] = {1,0,-1,0,1};
//3 这样每次是+dir[i],+dir[i+1]
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxn = 15;
bool vis[maxn][maxn];
int maze[maxn][maxn];
struct pos
{
int r,c;
int father;
pos(int _r = 0,int _c = 0,int _f = 0):r(_r),c(_c),father(_f){}
};
int dir[5] = {1,0,-1,0,1};
void bfs()
{
pos q[120];
//自己构造队列来实现广搜
int head = 0,tail = 1;
q[head] = pos(1,1,-1);
vis[1][1] = true;
int cnt = 0;
while(head != tail)
{
pos f = q[head];
if(f.r == n && f.c == m)
{
//找到了
vector<pos> vt;
while(true)
{
vt.push_back(f);
if(f.father == -1)
break;
f = q[f.father];
}
for(int i = vt.size()-1; i >= 0; --i)
{
cout << "(" << vt[i].r-1 << "," << vt[i].c-1 << ")"<< endl;
}
break;
}
for(int i = 0; i < 4; ++i)
{
int newR = dir[i] + f.r;
int newC = dir[i+1] + f.c;
if(!vis[newR][newC] && maze[newR][newC] == 0)
{
vis[newR][newC] = true;
q[tail++] = pos(newR,newC,head);
}
}
++head;
}
}
int main(){
#ifdef ONLINE_JUDGE
#else
freopen("E:/input.txt", "r", stdin);
#endif
while(cin >> n >> m)
{
fill(vis[0],vis[0]+maxn*maxn,true);
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
cin >> maze[i][j];
vis[i][j] = false;
}
}
bfs();
}
return 0;
}
编辑于 2020-03-14 23:11:46
回复(0)
问题信息
难度：
595条回答
4478收藏
103180浏览
通过挑战的用户
查看代码-
2023-03-11 16:31:38
-
2023-03-09 00:06:20
-
2023-03-05 12:23:54
-
2023-03-04 20:36:49 -
2023-03-04 13:41:15
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
