NowCoder最喜欢游乐场的迷宫游戏，他和小伙伴们比赛谁先走出迷宫。
现在把迷宫的地图给你，你能帮他算出最快走出迷宫需要多少步吗？
[编程题]走迷宫
- 热度指数：3969 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
输入包含多组数据。
每组数据包含一个10*10，由“#”和“.”组成的迷宫。其中“#”代表墙；“.”代表通路。
入口在第一行第二列；出口在最后一行第九列。
从任意一个“.”点都能一步走到上下左右四个方向的“.”点。
输出描述:
对应每组数据，输出从入口到出口最短需要几步。
示例1
输入
#.######## #........# #........# #........# #........# #........# #........# #........# #........# ########.# #.######## #........# ########.# #........# #.######## #........# ########.# #........# #.######.# ########.#
输出
16 30
我他么吐了啊，能不能把测试用例显示出来，草。 50%
#include <iostream>
(720)#include <vector>
#include <string>
(765)#include <algorithm>
using namespace std;
void DFS(vector<vector<char>>& vvc, int x, int y, int count,vector<vector<bool>>& books,int& min_)
{
if (x == 9 && y == 8)
{
min_ = min(min_, count);
return;
}
count++;
books[x][y] = true;
static int pos[4][2] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
for (int i = 0; i < 4; i++)
{
int nx = x + pos[i][0];
int ny = y + pos[i][1];
if (nx < 0 || ny < 0 || nx >= 10 || ny >= 10 || books[nx][ny] == true || vvc[nx][ny] == '#')
continue;
DFS(vvc, nx, ny, count,books,min_);
books[x][y] = false;
}
}
int main()
{
string s;
while(cin >> s)
{
vector<vector<bool>> books(10, vector<bool>(10, false));
vector<vector<char>> vvc(10, vector<char>(10));
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 10; j++)
{
if(i == 0)
vvc[i][j] = s[j];
else
cin >> vvc[i][j];
}
}
//(0,1)
int count = 0;
int min_ = 100;
DFS(vvc, 0, 1, count,books,min_);
cout << min_ << endl;
}
system("pause");
}
发表于 2020-03-13 23:52:07
回复(1)
import java.util.Scanner;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
while (s.hasNext()) {
boolean[][] map = new boolean[10][10];
int[][] steps = new int[10][10];
for (int i = 0; i < 10; i++) {
char[] lineChars = s.next().toCharArray();
for (int j = 0; j < lineChars.length; j++) {
if (lineChars[j] == '#') {
map[i][j] = true;
}
}
}
Queue<Point> queue = new LinkedList<>();
queue.add(new Point(1, 0));
int step = -1;
while (!queue.isEmpty()) {
Point cur = queue.poll();
if (cur.x == 8 && cur.y == 9) {
step = steps[9][8];
break;
}
for (Point next : new Point[]{
new Point(cur.x + 1, cur.y),
new Point(cur.x - 1, cur.y),
new Point(cur.x, cur.y + 1),
new Point(cur.x, cur.y - 1)}) {
if (next.x >= 0 && next.x < 10 && next.y >= 0 && next.y < 10
&& !map[next.y][next.x]) {
queue.add(next);
steps[next.y][next.x] = steps[cur.y][cur.x] + 1;
map[next.y][next.x] = true;
}
}
}
System.out.println(step);
}
}
static class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
典型的BFS
发表于 2018-08-18 14:48:22
回复(0)
import java.util.Scanner;
public class Main {
static int [][] fd = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 设置上下左右移动
static char [][] c = new char[10][10];
static int [][] num = new int [10][10];
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()){
for(int i = 0; i < 10; i++){
for(int j = 0; j < 10; j++){
num[i][j] = Integer.MAX_VALUE;
}
}
for(int i = 0; i < 10; i++){
c[i] = input.next().toCharArray();
}
num[0][1] = 0;
dfs(0, 1);
System.out.println(num[9][8]);
}
}
private static void dfs(int x, int y){
int xx, yy;
for(int i = 0; i < 4; i++){
xx = x + fd[i][0]; yy = y + fd[i][1];
if(0 <= xx && xx < 10 && yy < 10
&& yy >= 0 && c[xx][yy] == '.'){ // 坐标没有越界，还可以走、
if(num[xx][yy] > num[x][y] + 1){
num[xx][yy] = num[x][y] + 1;
dfs(xx, yy);
}
}
}
}
}
编辑于 2018-02-06 22:29:02
回复(0)
上一题稍微改一下
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>
using namespace std;
bool check(int x, int y, int m, int n, vector<vector<char>>& room)
{
return x >= 0 && x < m && y >= 0 && y < n && room[x][y] == '.';
}
int main(int argc, char** argv)
{
//freopen("in.txt", "r", stdin);
int m = 10, n = 10;
string row;
while (cin >> row)
{
vector<vector<char>> room(m, vector<char>(n));
for (int i = 0; i < m; ++i)
{
if (i > 0) cin >> row;
for (int j = 0; j < n; ++j)
{
room[i][j] = row[j];
}
}
int sx = 0, sy = 1;
int ex = 9, ey = 8;
vector<pair<int, int>> cur;
cur.emplace_back(sx, sy);
room[sx][sy] = ' ';
int step = 0;
bool reach = false;
while (!cur.empty())
{
vector<pair<int, int>> next;
for (auto& pr : cur)
{
if (pr.first == ex && pr.second == ey)
{
reach = true;
break;
}
int x = pr.first, y = pr.second;
if (check(x - 1, y, m, n, room))
{
room[x - 1][y] = ' ';
next.emplace_back(x - 1, y);
}
if (check(x + 1, y, m, n, room))
{
room[x + 1][y] = ' ';
next.emplace_back(x + 1, y);
}
if (check(x, y - 1, m, n, room))
{
room[x][y - 1] = ' ';
next.emplace_back(x, y - 1);
}
if (check(x, y + 1, m, n, room))
{
room[x][y + 1] = ' ';
next.emplace_back(x, y + 1);
}
}
if(reach) break;
++step;
cur = next;
}
cout << step << endl;
}
return 0;
}
发表于 2017-07-10 22:12:04
回复(0)
package test;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class migong {
static boolean[][] visited;
static int[][] direction = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
char[][] ch = new char[10][10];
while (in.hasNext()) {
visited = new boolean[10][10];
for (int i = 0; i < 10; i++) {
char[] temp = in.nextLine().toCharArray();
for (int j = 0; j < 10; j++) {
ch[i][j] = temp[j];
}
}
miNode start = new miNode(0, 1, 0);
miNode end = new miNode(9, 8, 0);
bfs(ch, start, end);
}
}
private static void bfs(char[][] ch, miNode start, miNode end) {
Queue<miNode> queue = new LinkedList<miNode>();
queue.add(start);
while (!queue.isEmpty()) {
miNode cur = queue.poll();
if (cur.x == end.x && cur.y == end.y) {
System.out.println(cur.step);
break;
}
for (int i = 0; i < 4; i++) {
miNode next = new miNode(cur.x + direction[i][0], cur.y + direction[i][1], cur.step + 1);
if (next.x >= 0 && next.x < 10 && next.y + direction[i][1] >= 0 && next.y + direction[i][1] < 10
&& ch[next.x][next.y] != '#' && !visited[next.x][next.y]) {
queue.add(next);
visited[next.x][next.y] = true;
}
}
}
}
static class miNode {
int x, y, step;
public miNode(int x, int y, int step) {
this.x = x;
this.y = y;
this.step = step;
}
}
}
发表于 2016-11-05 22:36:33
回复(0)
// dfs深度优先搜索
import java.util.*;
public class Main{
static int[][] direction = {{0,-1}, {-1,0}, {0,1}, {1,0}};
public static void dfs(int x, int y, char[][] maze, int[][] map){
for(int i = 0; i < 4; i++){
int xx = x + direction[i][0];
int yy = y + direction[i][1];
if(xx >= 0 && xx < 10 && yy >= 0 && yy < 10
&& maze[xx][yy] == '.' && map[xx][yy] > map[x][y]+1){
map[xx][yy] = map[x][y] + 1;
dfs(xx, yy, maze, map);
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
char[][] maze = new char[10][10];
int[][] map = new int[10][10];
for(int i = 0; i < 10; i++){
String str = sc.next();
for(int j = 0; j < 10; j++){
maze[i][j] = str.charAt(j);
map[i][j] = Integer.MAX_VALUE;
}
}
map[0][1] = 0;
dfs(0, 1, maze, map);
System.out.println(map[9][8]);
}
}
} // bfs广度优先搜索
import java.util.*;
public class Main{
static int[][] direction = {{0,-1}, {-1,0}, {0,1}, {1,0}};
static class Node{
int x, y;
public Node(int x, int y){
this.x = x;
this.y = y;
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
char[][] maze = new char[10][10];
int[][] map = new int[10][10];
boolean[][] visited = new boolean[10][10];
for(int i = 0; i < 10; i++){
String str = sc.next();
for(int j = 0; j < 10; j++){
maze[i][j] = str.charAt(j);
if(maze[i][j] == '#'){
visited[i][j] = true;
}
}
}
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(0, 1));
while(!queue.isEmpty()){
Node cur = queue.poll();
for(int i = 0; i < 4; i++){
Node next = new Node(cur.x+direction[i][0], cur.y+direction[i][1]);
if(next.x >= 0 && next.x < 10 && next.y >= 0 && next.y < 10
&& !visited[next.x][next.y]){
queue.offer(next);
map[next.x][next.y] = map[cur.x][cur.y] + 1;
visited[next.x][next.y] = true;
}
}
}
System.out.println(map[9][8]);
}
}
}
编辑于 2021-07-31 17:48:05
回复(0)
#include <iostream>
#include <vector>
#include <string>
#include <limits.h>
using namespace std;
vector<string> maze(10, string());
//ans存放最短路径，cur存放当前路径
void FindLeastSteps(int x, int y, int& ans, int cur)
{
if (x > 9 || y > 9 || x < 0 || y < 0 || maze[x][y] != '.')
return;
//这个地方的剪枝很关键!!! 在路径很多的时候，可以有效的防止多余的计算
if(cur > ans)
return;
//存储最短路径
if (x == 9 && y == 8)
{
if (ans > cur)
ans = cur;
return;
}
//我们将x,y走过的路径的位置变为1，
//这样就不用再开辟一个额外的used数组去记录已经走的路了
maze[x][y] = 1;
FindLeastSteps(x, y + 1, ans, cur + 1);
FindLeastSteps(x + 1, y, ans, cur + 1);
FindLeastSteps(x, y - 1, ans, cur + 1);
FindLeastSteps(x - 1, y, ans, cur + 1);
//回到上层递归时，要把当前所在位置重新设为'.' 代表没走这个位置
maze[x][y] = '.';
}
int main()
{
string s;
int i = 0;
while (getline(cin, s))
{
maze[i++] = s;
if (i == 10)
{
int ans = INT_MAX;
FindLeastSteps(0, 1, ans, 0);
cout << ans << endl;
i = 0;
}
}
return 0;
}
发表于 2021-11-26 23:04:04
回复(2)
//自己的一些看法，望各位批评指正
// BFS解法，利用了一个队列queue装载pair<int x,int y>类型数据(对应格子坐标)
//之所以使用queue，是因为队列的先进先出特性正好对应了
//广度优先搜索(BFS)的迭代
//个人认为这道题用BFS效率高些，与DFS相比因为没有使用递归反复更新格子里的值，
//时间复杂度较低，但题目迷宫较小所以运行时间没有太大差别。
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
int a[10][10] = {0};//记录格子状态，0代表没有走过
char str[10][10];//记录迷宫
int bfs(int x0,int y0)
{
queue<pair<int,int> > q;//存储格子坐标的队列
pair<int,int> p;
int x,y;
q.push(make_pair(x0,y0));
while(1)
{
p = q.front();
x = p.first;
y = p.second;
if(x==9&&y==8)//走到终点就退出循环
return a[9][8];
/*
下面是4个if语句，分别对应格子的上、下、左、右四个相邻的格子
如果这个格子符合条件(坐标不越界，同时不是'#'，并且之前没有走过)
就把它放入队列。这里需要注意的是，队列先进先出就保证了离出口近的
格子总是比离出口远的格子先处理，也就是说只有当广度(离出口距离比如2)
的所有格子都pop()出队列，广度为3的格子才变为队首元素。就这样一点点
增加广度，直到走到出口。
当然你也可以用一个for循环替代这里的4个if，但我想写的详细点*/
if((x-1)>=0&&(x-1)<=9&&y>=0&&y<=9&&a[x-1][y]==0&&str[x-1][y]!='#')
{
a[x-1][y]=a[x][y]+1;
q.push(make_pair(x-1,y));
}
if((x+1)>=0&&(x+1)<=9&&y>=0&&y<=9&&a[x+1][y]==0&&str[x+1][y]!='#')
{
a[x+1][y]=a[x][y]+1;
q.push(make_pair(x+1,y));
}
if(x>=0&&x<=9&&(y-1)>=0&&(y-1)<=9&&a[x][y-1]==0&&str[x][y-1]!='#')
{
a[x][y-1]=a[x][y]+1;
q.push(make_pair(x,y-1));
}
if(x>=0&&x<=9&&(y+1)>=0&&(y+1)<=9&&a[x][y+1]==0&&str[x][y+1]!='#')
{
a[x][y+1]=a[x][y]+1;
q.push(make_pair(x,y+1));
}
q.pop();//判断完上下左右4个格子后该格子应该出队
}
}
int main()
{
char c;
while(~scanf("%c",&c))
{
str[0][0] = c;
for(int i=1;i<10;i++)
{
scanf("%c",&c);
str[0][i] = c;
}
getchar();//吃掉末尾的换行符
for(int i=1;i<10;i++)
{
for(int j=0;j<10;j++)
{
scanf("%c",&c);
str[i][j] = c;
}
getchar();//吃掉末尾的换行符
}
printf("%d\n",bfs(0,1));
memset(a,0,sizeof(a));//初始化全局变量a数组
}
return 0;
}
//下面是DFS解法，个人认为没有BFS效率高
//DFS深度优先搜索就是一条道走到黑，然后再回来，比原值小就更新原值
//所以遍历次数可能更多一点，另外DFS使用了递归
#include<iostream>
#include<string.h>
using namespace std;
int a[10][10] = {0};
char str[10][10];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
void dfs(int x,int y)
{
for(int i=0;i<4;i++)
{
int m = x+dir[i][0];
int n = y+dir[i][1];
if(m>=0&&m<=9&&n>=0&&n<=9&&str[m][n]!='#')
{
if((a[m][n]==0)||(a[x][y]+1)<a[m][n])
{
a[m][n] = a[x][y]+1;
dfs(m,n);
}
}
}
}
int main()
{
// freopen("input.txt","r",stdin);
char c;
while(~scanf("%c",&c))
{
str[0][0] = c;
for(int i=1;i<10;i++)
{
scanf("%c",&c);
str[0][i] = c;
}
getchar();
for(int i=1;i<10;i++)
{
for(int j=0;j<10;j++)
{
scanf("%c",&c);
str[i][j] = c;
}
getchar();
}
dfs(0,1);
printf("%d\n",a[9][8]);
memset(a,0,sizeof(a));
}
return 0;
}
发表于 2018-04-03 22:58:43
回复(1)
1、深度优先遍历
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
char str[][] = new char[10][10];
int[][] dp = new int[10][10];//动归数组
while (scanner.hasNext()) {
for (int i = 0; i < 10; i++) {
String ret = scanner.next();
for (int j = 0; j < 10; j++) {
str[i][j] = ret.charAt(j);
dp[i][j] = Integer.MAX_VALUE;
}
}
dp[0][1] = 0;
dfs(str, 0, 1, dp);
System.out.println(dp[9][8]);
}
}
private static void dfs(char[][] str, int i, int j, int[][] dp) {
//i j坐标不是终点
int[][] pos = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//有四个方向 上下左右
for (int k = 0; k < 4; k++) {//控制点的四个方向
// 沿着一个树的分支 走到终点
int x = i + pos[k][0];
int y = j + pos[k][1];
if (x >= 0 && x < 10 && y >= 0 && y < 10 && str[x][y] == '.' && dp[x][y] > dp[i][j] + 1) {
//不越界 并且是通路 并且没有到达过
// 如果说已经dp[x][y]已经是从入口到达（x，y）的最短路径了 就不需要从这个点开始找寻最短路径了 因为这个点已经在最短路径之中了
//如果某一个路径经过这个点的距离更小，这个路径才有可能会是最短路径
dp[x][y] = Math.min(dp[i][j] + 1, dp[x][y]);//dp[x][y]保存到达（x，y）下标的最短路径
if (x == 9 && y == 8) {//找到了其中一个路径 回溯 dp[x][y]保留路径的最终长度
return;
}
dfs(str, x, y, dp);//沿着一个树的分支 走到终点
//递归结束之后 回溯 在for循环的控制下 找到新的路径
}
}
}
}
深度优先遍历，求多个树的路径，后得出最小的，虽然有动归的优化，但是还是会重复许多不必要的结点
2、广度优先遍历
二叉树的层次遍历，从根节点到指定叶子节点 的层数
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Note {
int x;
int y;
public Note(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
char str[][] = new char[10][10];
while (scanner.hasNext()) {
for (int i = 0; i < 10; i++) {
String ret = scanner.next();
for (int j = 0; j < 10; j++) {
str[i][j] = ret.charAt(j);
}
}
System.out.println(bfs(str));
}
}
private static int bfs(char[][] str) {
Queue<Note> queue = new LinkedList();
boolean flag[][] = new boolean[10][10];//用于标识元素是否已经被使用
int max = 0;
int[][] pos = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};//有四个方向 上下左右
//第一层 放入根
Note note = new Note(0, 1);
queue.add(note);
flag[0][1] = true;
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
note = queue.poll();
//存入这个结点 可以下 右 左 上到的移动的位置
int x = note.x;
int y = note.y;
if (x == 9 && y == 8)///最后从队列取得元素 是出口就结束了
return max;
flag[x][y] = true;//得到 这层元素的下一层元素 这个结点已经被使用
for (int i = 0; i < 4; ++i) {//控制四个方向
int posi = x + pos[i][0];
int posj = y + pos[i][1];
if (posi >= 0 && posi <= 9 && posj >= 0 && posj <= 9 && !flag[posi][posj] && str[posi][posj] == '.') {
Note note1 = new Note(posi, posj);
queue.add(note1);
}
}
}
//统计完一层结点的下一个位置 也就是获取了一层元素
max++;
}
return max;
}
}
import java.util.Queue;
import java.util.Scanner;
class Note {
int x;
int y;
public Note(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
char str[][] = new char[10][10];
while (scanner.hasNext()) {
for (int i = 0; i < 10; i++) {
String ret = scanner.next();
for (int j = 0; j < 10; j++) {
str[i][j] = ret.charAt(j);
}
}
System.out.println(bfs(str));
}
}
private static int bfs(char[][] str) {
Queue<Note> queue = new LinkedList();
boolean flag[][] = new boolean[10][10];//用于标识元素是否已经被使用
int max = 0;
int[][] pos = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};//有四个方向 上下左右
//第一层 放入根
Note note = new Note(0, 1);
queue.add(note);
flag[0][1] = true;
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
note = queue.poll();
//存入这个结点 可以下 右 左 上到的移动的位置
int x = note.x;
int y = note.y;
if (x == 9 && y == 8)///最后从队列取得元素 是出口就结束了
return max;
flag[x][y] = true;//得到 这层元素的下一层元素 这个结点已经被使用
for (int i = 0; i < 4; ++i) {//控制四个方向
int posi = x + pos[i][0];
int posj = y + pos[i][1];
if (posi >= 0 && posi <= 9 && posj >= 0 && posj <= 9 && !flag[posi][posj] && str[posi][posj] == '.') {
Note note1 = new Note(posi, posj);
queue.add(note1);
}
}
}
//统计完一层结点的下一个位置 也就是获取了一层元素
max++;
}
return max;
}
}
发表于 2022-09-30 22:49:51
回复(1)
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int ans = 0;
vector<vector<int>> dirs = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
bool isvalid(vector<string>& map, int i, int j) {
return i >= 0 && i < 10 && j >= 0 && j < 10 && map[i][j] == '.';
}
void DFS(vector<string>& map, int i, int j, int cur) {
if (!isvalid(map, i, j) || cur >= ans) return;
if (i == 9 && j == 8) {
ans = cur;
return;
}
map[i][j] = '#';
for (int k = 0; k < 4; k++) {
DFS(map, i + dirs[k][0], j + dirs[k][1], cur + 1);
}
map[i][j] = '.';
}
int main() {
vector<string> map(10);
while (getline(cin, map[0])) {
for (int i = 1; i <= 9; i++)
getline(cin, map[i]);
ans = 0x3fffffff;
DFS(map, 0, 1, 0);
cout << ans << endl;
}
return 0;
}
发表于 2023-09-07 21:27:03
回复(0)
BFS可解，和上题“红与黑”思路基本相同。
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
struct pos { int x, y, level; };
int bfs(vector<vector<char> > & map)
{
const int dir[4][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } };
queue<pos> que;
int m = map.size(), n = map[0].size();
vector<vector<bool> > visit(m, vector<bool>(n, false));
pos start{ 0,1,0 }, end{ 9,8,0 };
que.push(start);
visit[start.x][start.y] = true;
while (!que.empty())
{
pos cur = que.front(), next;
que.pop();
for (int i = 0; i < 4; ++i)
{
next.x = cur.x + dir[i][0];
next.y = cur.y + dir[i][1];
next.level = cur.level + 1;
if (next.x == end.x && next.y == end.y) return next.level;
if (next.x >= 0 && next.x < m && next.y >= 0 && next.y < n && \
!visit[next.x][next.y] && map[next.x][next.y] == '.')
{
que.push(next);
visit[next.x][next.y] = true;
}
}
}
return 0;
}
int main()
{
vector<vector<char> > map(10, vector<char>(10));
while (cin >> map[0][0])
{
for (int i = 0; i < 10; ++i)
for (int j = 0; j < 10; ++j)
{
if (i == 0 && j == 0) continue;
cin >> map[i][j];
}
cout << bfs(map) << endl;
}
return 0;
}
发表于 2015-12-15 21:36:50
回复(0)
深度优先遍历的思想是用回溯法把每条路径都走通，然后找出最短的那条；但这题用广度优先遍历算法更好，思想就是从起点开始，把每个能走到的节点都放进队列保存起来，之后轮到它出队列的时候将它上下左右能到达且未走过的节点再放进队列里面去，相当于“在这条路径走了1步”，因为它放进来的节点本质上又是几条新路径，核心思想就在于：假设有X条路径,那么每一轮就相当于在X条路径中各走一步(非通路中途会被淘汰掉，因为没有这条路径的新节点能入队了), 最后一定是在最短的通路中率先抵达终点
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
static const int N = 10;
struct Node
{
Node(int _i,int _j,int _counts):i(_i),j(_j),counts(_counts)
{
if (flags[0].empty())
{
for (int i = 0; i < flags.size(); i++)
flags[i].resize(N, true);
}
flags[i][j] = false;//当创建某个即将要走到的节点时,自动设置对应flags为禁止再走
}
static bool getflag(int _i, int _j)
{
return flags[_i][_j];
}
static void clear()
{
for (int i = 0; i < flags.size(); i++)
flags[i].clear();
}
int i;//该节点横坐标
int j;//该节点纵坐标
int counts;//到该节点为止走了多少步
static vector<vector<bool>> flags;//统计每个节点是否可以走,true为未走过,可以走;false为已走过,禁止再走
};
vector<vector<bool>> Node::flags(N);
int solout(vector<string>&map)//广度优先遍历,结合该题具体场景,核心思想是假设有X条路,那么每一轮相当于在X条路中各走一步(非通路中途淘汰掉),最后一定是在最短的通路中率先抵达终点
{
queue<Node> path;
path.push(Node(0, 1, 0));
while (!path.empty())
{
Node& tmp = path.front();
int i = tmp.i;
int j = tmp.j;
int counts = tmp.counts;
if (i == N-1 && j == N-2)//已到达终点
return counts;
//探寻该节点下右上左是否有节点可以被走到
if (map[i + 1][j] == '.' && Node::getflag(i + 1, j))
path.push(Node(i + 1, j, counts + 1));
if(map[i][j+1] == '.' && Node::getflag(i , j+1))
path.push(Node(i , j+1, counts + 1));
if (i>0&&map[i-1][j] == '.' && Node::getflag(i-1, j ))
path.push(Node(i - 1, j , counts + 1));
if (map[i ][j-1] == '.' && Node::getflag(i , j-1))
path.push(Node(i , j-1, counts + 1));
path.pop();
}
return 0;
}
int main()
{
vector<string>map(N);
while (getline(cin, map[0]))
{
for (int i = 1; i < N; i++)
getline(cin, map[i]);
cout << solout(map) << endl;
Node::clear();
}
return 0;
}
编辑于 2023-08-20 01:49:17
回复(0)
#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
int bfs(vector<string>& g, int sx, int sy, int dx, int dy) {
queue<pair<int, int>> q;
q.emplace(sx, sy);
int step = 0;
vector<vector<int>> dir {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
while (!q.empty()) {
size_t sz = q.size();
++step;
for (int i = 0; i < sz; ++i) {
auto front = q.front();
q.pop();
for (int j = 0; j < dir.size(); ++j) {
int x = front.first + dir[j][0];
int y = front.second + dir[j][1];
if (x == dx && y == dy) return step;
if (x < 0 || x >= g.size() || y < 0 || y >= g[0].size() || g[x][y] != '.') continue;
g[x][y] = '#'; //visited
q.emplace(x, y);
}
}
}
return -1;
}
int main() {
//read 10*10 matrix
string line;
while (getline(cin, line)) {
vector<string> g;
g.emplace_back(line);
for (int i = 0; i < 9; ++i) {
getline(cin, line);
g.emplace_back(line);
}
//bfs search
cout << bfs(g, 0, 1, 9, 8) << endl;
}
}
发表于 2022-11-09 10:14:48
回复(0)
// write your code here cpp
#include<iostream>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e2 + 10; //110
vector<vector<char> > g(10, vector<char>(10));
int d[N][N]; //g[N][N]设置迷宫,d[N][N]遍历到的点到起点的距离(按照广度优先搜索的距离)
int bfs()
{
//dx数组代表点的横坐标往上,往右,往下,往左;dy数组代表点的纵坐标
int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
queue<PII> q; //代表点的坐标,从(0,1)开始
//将二维数组d初始化为-1,表示所有点没有被遍历过
for(auto& v : d)
{
for(auto& x : v)
{
x = -1;
}
}
d[0][1] = 0; //第一个被遍历的点
q.push({0,1});
while(!q.empty())
{
auto t = q.front();
q.pop();
//该点往四个方向的搜索,均是该点广度优先搜索的下一个
for(int i = 0; i < 4; i++)
{
int x = t.first + dx[i],y = t.second + dy[i];
//g[x][y]==0代表该点可以走,d[x][y]==-1表示该点没有被遍历,因为要求最短距离,
//同一个点若是重复了,则不是最短距离
if(x>=0 && x<10 && y>=0 && y<10 && g[x][y]=='.' && d[x][y]==-1)
{
d[x][y] = d[t.first][t.second]+1;
q.push({x,y});
}
}
}
return d[9][8];
}
int main()
{
while (cin >> g[0][0])
{
for (int i = 0; i < 10; ++i)
for (int j = 0; j < 10; ++j)
{
if (i == 0 && j == 0) continue;
cin >> g[i][j];
}
cout << bfs() << endl;
}
return 0;
}
发表于 2022-10-25 20:35:55
回复(0)
A*算法 通过对比当前路径到达终点所需的最小代价来进行计算
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
char[][] map = new char[10][10];
while(sc.hasNext()){
for(int i = 0;i < 10;i++){
map[i] = sc.next().toCharArray();
}
Queue<BetterWay> queue = new PriorityQueue<>();
queue.add(new BetterWay(0,1,0,0));
while(!queue.isEmpty()){
BetterWay bw = queue.poll();
if(bw.nextCost == 0){
System.out.println(bw.size);
break;
}
int x = bw.x;
int y = bw.y;
int nowCost = bw.nowCost;
int size = bw.size;
map[x][y] = '#';
if(checkWay(map,x-1,y)){
queue.add(new BetterWay(x-1,y,nowCost,size+1));
}
if(checkWay(map,x+1,y)){
queue.add(new BetterWay(x+1,y,nowCost,size+1));
}
if(checkWay(map,x,y-1)){
queue.add(new BetterWay(x,y-1,nowCost,size+1));
}
if(checkWay(map,x,y+1)){
queue.add(new BetterWay(x,y+1,nowCost,size+1));
}
}
}
}
private static boolean checkWay(char[][] map ,int x , int y){
return x >=0 && x < 10 && y >=0 && y < 10 && map[x][y] == '.';
}
private static class BetterWay implements Comparable<BetterWay>{
int x;
int y;
int prevCost;
int nextCost;
int nowCost;
int size;
public BetterWay(int x, int y,int prevCost,int size){
this.x = x;
this.y = y;
this.prevCost = prevCost;
this.nextCost = (9 - x) + (8 - y);
this.nowCost = this.prevCost + this.nextCost;
this.size = size;
}
public int compareTo(BetterWay bw){
return this.nowCost - bw.nowCost;
}
}
}
编辑于 2022-05-22 23:41:21
回复(1)
import java.util.*;
class Position{
int x;
int y;
int level;
public Position(int x,int y,int level){
this.x = x;
this.y = y;
this.level = level;
}
}
public class Main {
public static int bfs(char[][] s,int m,int n){
int[][] direc = {{-1,0},{0,1},{1,0},{0,-1}};
//迷宫的入口和出口
Position enter = new Position(0,1,0);
Position out = new Position(9,8,0);
//标记走过得数组
boolean[][] flg = new boolean[m][n];
//采用广度优先方式进行遍历
Queue<Position> queue = new LinkedList<>();
queue.offer(enter);
while(!queue.isEmpty()){
Position cur = queue.poll();
flg[cur.x][cur.y] = true;
//如果已经到了出口的位置，则直接返回
if(cur.x == out.x && cur.y == out.y){
return cur.level;
}
for(int i = 0;i < 4;i++){
Position next = new Position(cur.x + direc[i][0],cur.y + direc[i][1],cur.level + 1);
//数组下标没有越界，并且该点是合法路径，并且还没有被标记过
if(next.x >= 0 && next.x < 10 && next.y >= 0 && next.y < 10 &&
s[next.x][next.y] == '.' && !flg[next.x][next.y]){
queue.offer(next);
}
}
}
return 0;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
char[][] map = new char[10][10];
for(int i = 0;i < 10;i++){
String s = sc.next();
for(int j = 0;j < 10;j++){
map[i][j] = s.charAt(j);
}
}
System.out.println(bfs(map,10,10));
}
}
} 。
编辑于 2022-06-06 15:10:35
回复(0)
import sys
inp=''
for l in sys.stdin:
inp+=l.replace('\n', '')
manylines=[]
inp=''
for l in sys.stdin:
inp+=l.replace('\n', '')
manylines=[]
lines = []
count=0
count=0
for i in range(0,len(inp)+1,10):
if count==10:
manylines.append(lines)
lines=[]
count=0
line = list(inp[i:i + 10])
lines.append(line)
count+=1
if count==10:
manylines.append(lines)
lines=[]
count=0
line = list(inp[i:i + 10])
lines.append(line)
count+=1
graphs=[]
for lines in manylines:
graph={}
for i in range(len(lines)):
for j in range(len(lines[i])):
graph[str(i)+str(j)]=[]
if lines[i][j]=='#':
continue
if j>0:
if lines[i][j-1] =='.': graph[str(i)+str(j)].append(str(i)+str(j-1))
if j+1<len(lines[i]):
if lines[i][j+1] == '.': graph[str(i) + str(j)].append(str(i) + str(j + 1))
if i > 0:
if lines[i-1][j] == '.': graph[str(i) + str(j)].append(str(i-1) + str(j))
if i+1<len(lines):
if lines[i+1][j] == '.': graph[str(i) + str(j)].append(str(i+1) + str(j))
graphs.append(graph)
for lines in manylines:
graph={}
for i in range(len(lines)):
for j in range(len(lines[i])):
graph[str(i)+str(j)]=[]
if lines[i][j]=='#':
continue
if j>0:
if lines[i][j-1] =='.': graph[str(i)+str(j)].append(str(i)+str(j-1))
if j+1<len(lines[i]):
if lines[i][j+1] == '.': graph[str(i) + str(j)].append(str(i) + str(j + 1))
if i > 0:
if lines[i-1][j] == '.': graph[str(i) + str(j)].append(str(i-1) + str(j))
if i+1<len(lines):
if lines[i+1][j] == '.': graph[str(i) + str(j)].append(str(i+1) + str(j))
graphs.append(graph)
def BFS(graph,start,end):
queue=[]
queue.append(start)
seen=set()
seen.add(start)
parent={start:None}
while len(queue)>0:
vertex=queue.pop(0)
nodes=graph[vertex]
for w in nodes:
if w not in seen:
queue.append(w)
seen.add(w)
parent[w]=vertex
rall=[]
while end!=None:
rall.append(end)
end=parent[end]
return rall
for g in graphs:
# print(g)
lj=BFS(g,'01','98')
print(len(lj)-1)
queue=[]
queue.append(start)
seen=set()
seen.add(start)
parent={start:None}
while len(queue)>0:
vertex=queue.pop(0)
nodes=graph[vertex]
for w in nodes:
if w not in seen:
queue.append(w)
seen.add(w)
parent[w]=vertex
rall=[]
while end!=None:
rall.append(end)
end=parent[end]
return rall
for g in graphs:
# print(g)
lj=BFS(g,'01','98')
print(len(lj)-1)
发表于 2022-04-06 09:43:37
回复(0)
#include <stdio.h>
char map[10][10];
struct mi{
int x;
int y;
};
void BFS(int a, int b);
int main()
{
char z;
while (scanf("%c",&z)!=EOF) {
map[0][0] = z;
int i, j;
for (i = 1; i < 10; i++) map[0][i] = getchar();
getchar();
for (i = 1; i < 10; i++) {
for (j = 0; j < 10; j++){
map[i][j] = getchar();
}
getchar();
}
BFS(0, 1);
int x = 9, y = 8, k;
int cnt = 0;
printf("%d\n", map[9][8]);
}
return 0;
}
void BFS(int a, int b)
{
int xx[4] = {0, 0, 1, -1};
int yy[4] = {1, -1, 0, 0};
struct mi A;
A.x = a;
A.y = b;
struct mi queue[100];
int front = -1, rear = -1;
queue[++rear] = A;
map[a][b] = 0;
int zx, zy, i;
while (rear != front) {
struct mi temp;
temp = queue[++front];
if (temp.x == 9 && temp.y == 8) break;
for (i = 0; i < 4; i++) {
zx = temp.x + xx[i];
zy = temp.y + yy[i];
if (zx >= 10 || zx < 0 || zy >= 10 || zy < 0 || map[zx][zy] != '.') continue;
map[zx][zy] = map[temp.x][temp.y] + 1;
struct mi kao;
kao.x = zx;
kao.y = zy;
queue[++rear] = kao;
}
}
}
char map[10][10];
struct mi{
int x;
int y;
};
void BFS(int a, int b);
int main()
{
char z;
while (scanf("%c",&z)!=EOF) {
map[0][0] = z;
int i, j;
for (i = 1; i < 10; i++) map[0][i] = getchar();
getchar();
for (i = 1; i < 10; i++) {
for (j = 0; j < 10; j++){
map[i][j] = getchar();
}
getchar();
}
BFS(0, 1);
int x = 9, y = 8, k;
int cnt = 0;
printf("%d\n", map[9][8]);
}
return 0;
}
void BFS(int a, int b)
{
int xx[4] = {0, 0, 1, -1};
int yy[4] = {1, -1, 0, 0};
struct mi A;
A.x = a;
A.y = b;
struct mi queue[100];
int front = -1, rear = -1;
queue[++rear] = A;
map[a][b] = 0;
int zx, zy, i;
while (rear != front) {
struct mi temp;
temp = queue[++front];
if (temp.x == 9 && temp.y == 8) break;
for (i = 0; i < 4; i++) {
zx = temp.x + xx[i];
zy = temp.y + yy[i];
if (zx >= 10 || zx < 0 || zy >= 10 || zy < 0 || map[zx][zy] != '.') continue;
map[zx][zy] = map[temp.x][temp.y] + 1;
struct mi kao;
kao.x = zx;
kao.y = zy;
queue[++rear] = kao;
}
}
}
发表于 2020-04-05 16:03:52
回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int res=__INT_MAX__;
vector<vector<int>>visited(10,vector<int>(10,0));
void find_path(vector<vector<char>>&m,int sx,int sy,int tx,int ty,int tmp){
if(sx<0||sy<0||visited[sx][sy]||sx>=10||sy>=10)return;
if(m[sx][sy]=='#')return;
if(tmp>res)return;
if(sx==tx&&sy==ty){if(tmp<res)res=tmp;return;}
visited[sx][sy]=1;
find_path(m,sx-1,sy,tx,ty,tmp+1);
find_path(m,sx,sy-1,tx,ty,tmp+1);
find_path(m,sx+1,sy,tx,ty,tmp+1);
find_path(m,sx,sy+1,tx,ty,tmp+1);
visited[sx][sy]=0;
}
int main(){
string s;
while(cin>>s){
res=__INT_MAX__;
vector<vector<char>>m(10,vector<char>(10));
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
if(i==0)m[i][j]=s[j];
else cin >> m[i][j];
}
}
find_path(m,0,1,9,8,0);
cout << res << endl;
}
return 0;
} 没什么效率的递归DFS，不同的是搜索过程中递归完毕需要释放掉visited，，另外累积路径长度已经大于当前最小的结果时，可以中断不再搜索。。面试刚遇到过。
发表于 2019-08-24 14:25:40
回复(0)
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
char maze[10][10];
int dist[10][10];
int vis[10][10];
int a[4][2]={-1,0,
1,0,
0,-1,
0,1};
queue<int> qu;
void bfs(int x,int y)
{
vis[x][y]=1;
dist[x][y]=0;
qu.push(x*10+y);
while(!qu.empty())
{
int m,n,nx,ny;
int t=qu.front();
m = t/10;
n=t%10;
qu.pop();
for(int i=0;i<4;i++)
{
nx=m+a[i][0];
ny=n+a[i][1];
if(nx<0 || nx>9 || ny < 0 || ny>9 || vis[nx][ny]== 1|| maze[nx][ny]=='#')
continue;
dist[nx][ny]=dist[m][n]+1;
vis[nx][ny]=1;
if(nx == 9&&ny==8)
return;
qu.push(nx*10+ny);
}
}
}
int main()
{
char z;
while(scanf("%c",&z)!=EOF)
{
for(int i=0;i<10;i++)
{
for(int j=0;j<10;j++)
{
if(i==0&&j==0)
maze[i][j]=z;
else
scanf("%c",&maze[i][j]);
}
getchar();
}
while(!qu.empty())qu.pop();
memset(vis,0,sizeof(vis));
bfs(0,1);
printf("%d\n",dist[9][8]);
}
return 0;
}
发表于 2019-07-31 15:11:30
回复(0)
问题信息
难度：
33条回答
44收藏
19292浏览
通过挑战的用户
查看代码-
2023-03-04 21:46:04
-
2023-02-10 21:00:08 -
2023-01-08 21:26:00
-
2023-01-06 19:10:55 -
2022-12-28 17:34:48
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
