首页 > 试题广场 >

迷宫寻宝-研发

[编程题]迷宫寻宝-研发
  • 热度指数:1170 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解

一位冒险者进入了一个迷宫中寻宝。他手上已经拥有了一份这个迷宫的地图,其中标注了迷宫的完整结构以及迷宫中每个宝箱所在的位置。

迷宫的地图是一个由m*n个格子组成的平面图,纵向的上下方向上每列有m个格子,横向的左右方向上每行有n个格子,其中每个格子为不能进入的障碍格或可以进入的通行格。如果有两个上下相邻或左右相邻的通行格,则可以从其中一个通行格走到另一个通行格。每个宝箱放置在不同的通行格中。

他的目标是收集到这个迷宫里的所有宝箱,因此他给自己在这个迷宫中寻宝制定了如下策略:

1. 计算出离他当前位置曼哈顿距离最小的未收集宝箱,如果有多个就选定最小编号那个,记为k号宝箱;

2. 如果他当前位置无法到达k号宝箱,则收集失败,流程结束;否则,计算出他当前位置到k号宝箱的最短路径长度,并且按上下左右的次序依次计算出如果向这个方向走一格通行格之后,到k号宝箱的最短路径长度是否有缩短,如果有缩短则往这个方向走一格;

3. 如果他当前所在位置有未收集宝箱,就收集这个宝箱。如果所有宝箱已经被收集,则收集完成。否则回到第1步并重复执行。

其中迷宫中两个位置的曼哈顿距离,是指这两个位置在上下方向的行差,加上左右方向的列差。如果用公式表示,如果两个位置分别为(x, y)和(u, v),则这两个位置的曼哈顿距离为|x-u|+|y-v|。

两个位置间的一条路径,是指从其中一个位置开始,通过若干个相邻通行格,走到另一个位置,其中经过的通行格顺序。两个位置的最短路径,是指这两个位置的所有路径中,通过的通行格数量最少的路径。两个位置的最短路径长度,是指沿这两个位置的最短路径走的格数。

问在这种策略下收集所有宝箱,他需要走多少格?

数据范围:
进阶:时间复杂度,空间复杂度

输入描述:

输入第一行为一个正整数T,表示有T组数据。

每组数据的第一行为两个正整数m和n,分别表示迷宫地图的行数和列数。

接下来有m行,每行有n个字符,表示迷宫地图中这行每一个中的图例表示。图例如下:

#: 障碍格;

*: 冒险者当前位置,为通行格;

0-9: 每个宝箱所在位置,为通行格;

.: 其它通行格

其中冒险者当前位置在一个迷宫地图中是有且仅有一个的。表示宝箱的数字,在一个迷宫地图中最多只会出现一次,且如果有一个k(k>0)号宝箱在迷宫地图中,则k-1号宝箱也必定会在迷宫地图中。

 

数据范围:

对于所有数据,满足1<=T<=5, 1<=m<=50, 1<=n<=50。



输出描述:

对于每一组数据,输出一个正整数。如果冒险者能收集完所有宝箱,则输出他共走了多少格,否则输出-1。

示例1

输入

3
5 5
0...1
.#.#.
..*..
.#.#.
2...3
5 5
0...1
.#.#.
..*.#
.#.#.
2.#.3
5 5
....1
.####
..*..
####.
0....

输出

16
-1
-1

说明


在第一组数据中,冒险者先向上走2格,再向左走2格,收集了0号宝箱;然后向右走4格,收集了1号宝箱;然后向下走4格,收集了3号宝箱;再然后向右走4格,收集了2号宝箱,收集所有宝箱完成,共走了2+2+4+4+4=16格。

在第二组数据中,无法从当前位置走到3号宝箱所在的位置收集3号宝箱,因此无法完成收集所有宝箱的任务。

在第三组数据中,在初始位置依次执行策略:

1. 计算出与0号宝箱的曼哈顿距离为4,与1号宝箱的曼哈顿距离为4,因此选定0号宝箱;

2. 计算出当前位置到0号宝箱的最短路径长度为8,按上下左右的次序依次计算:

(1) 上方为障碍格,忽略;

(2) 下方为障碍格,忽略;

(3) 左方为通行格,如果走到左方的通行格,则到0号宝箱的最短路径长度为9,比当前的最短路径长度8大,因此不选择;

(4) 右方为通行格,如果走到右方的通行格,则到0号宝箱的最短路径长度为7,比当前的最短路径长度8小,因此向这个方向走一格。

3. 当前未收集完所有宝箱,回到策略步骤1继续执行;

4. 计算出与0号宝箱的曼哈顿距离为5,与1号宝箱的曼哈顿距离为3,因此选定1号宝箱;

5. 计算出当前位置到1号宝箱的最短路径长度为9,按上下左右的次序依次计算:

(1) 上方为障碍格,忽略;

(2) 下方为障碍格,忽略;

(3) 左方为通行格,如果走到左方的通行格,则到1号宝箱的最短路径长度为8,比当前的最短路径长度9大,因此向这个方向走一格;

6. 当前未收集完所有宝箱,回到策略步骤1继续执行。

要注意到此时,冒险者当前在初始位置上,且所有宝箱都还没有被收集,继续按策略执行的过程中,冒险者会在这个位置向右走一格再向左走一格的循环中,永远无法收集到所有宝箱。



#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
int paihui = 0;
char mhd_min(unordered_map<char, vector<int>>& pos, int boxNum, set<int>&findBox, int m, int n) {
	int min_len = m + n; char res;
	for (int i = 0; i < boxNum; i++) {
		if (findBox.find(i) != findBox.end())continue;
		int len = abs(pos[( '0'+i)][0] - pos['a'][0]) + abs(pos[('0'+i)][1] - pos['a'][1]);
		if (len < min_len) {
			min_len = len;
			res = (i + '0');
		}
	}
	return res;
}
int bfs(vector<string>& mmap, unordered_map<char, vector<int>>& pos, int x, int y, char target,int m,int n) {
	int len = 0;
	queue<pair<int, int>>que;;
	int walked[50][50];
	vector<pair<int, int>>way{ {0,-1},{0,1},{-1,0},{1,0} };
	que.push({ x,y });
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			walked[i][j] = 2500;
		}
	}
	walked[x][y] = 0;
	while (!que.empty()) {
		pair<int, int>head = que.front();
		que.pop();		
		if (head.first == pos[target][0] && head.second == pos[target][1])return walked[pos[target][0]][pos[target][1]];
		for (int i = 0; i < 4; i++) {
			int newx = head.first + way[i].first, newy = head.second + way[i].second;
			if ((newx >= 0) && (newx < m) && (newy>= 0) && (newy < n)) {				
				if ((mmap[newx][newy] == '.'||mmap[newx][newy]==target)&& walked[newx][newy] == 2500)
				{
					que.push({ newx,newy });
					walked[newx][newy] = walked[head.first][head.second] + 1;
				}

			}
		}
	}
	return m * n;
}
bool check(pair<int, int>way, vector<string>& mmap, unordered_map<char, vector<int>>& pos, int m, int n, char target, set<int>&finded) {
	int nextx = pos['a'][0] + way.first, nexty = pos['a'][1] + way.second;
	if (nextx<0 || nextx>m - 1 || nexty<0 || nexty>n - 1 || mmap[nextx][nexty] == '#')return false;
	if (isdigit(mmap[nextx][nexty])) {
		finded.insert(mmap[nextx][nexty] - '0');
		mmap[nextx][nexty] = '.';
		return true;
	}
	int olen = bfs(mmap, pos, pos['a'][0], pos['a'][1], target, m, n);
	int nlen = bfs(mmap, pos, nextx, nexty, target, m, n);
	if (nlen < olen && nlen < m*n)return true;
	else return false;
}
int findBox(vector<string>& mmap, unordered_map<char, vector<int>>& pos, int m, int n, int boxNum, set<int>&finded) {
	if (boxNum == finded.size()) {
		return 0;
	}
	vector<pair<int, int>>way{ {0,-1},{0,1},{-1,0},{1,0} };
	char target = mhd_min(pos, boxNum, finded, m, n);
	for (int i = 0; i < 4; i++) {
		if (check(way[i], mmap, pos, m, n, target, finded)) {
			int newx= pos['a'][0] + way[i].first,newy =  pos['a'][1] + way[i].second;
			if (newx == pos['a'][2] && newy == pos['a'][3]) {
				paihui++;
				if (paihui > 2)return -1;
			}
			else paihui = 0;
			pos['a'][2] = pos['a'][0]; pos['a'][3] = pos['a'][1]; pos['a'][0] = newx; pos['a'][1] = newy;
			int res = findBox(mmap, pos, m, n, boxNum, finded);
			if (res == -1) {
				return -1;
			}
			else {
				return ++res;
			}
			break;
		}
	}
	return -1;
}


int main() {
	int group;
	cin >> group;
	for (int i = 0; i < group; i++) {
		int m, n, boxNum = 0;
		cin >> m >> n;
		vector<string> mmap(m);//记录地图
		unordered_map<char, vector<int>>pos;//记录各个宝箱位置
		for (int j = 0; j < m; j++) {
			cin >> mmap[j];
			for (int k = 0; k < n; k++) {
				if (mmap[j][k] == '.' || mmap[j][k] == '#')continue;
				if (isdigit(mmap[j][k])) {
					boxNum = max(boxNum, mmap[j][k] - '0');
					pos[mmap[j][k]] = { j,k,m + n };
					continue;
				}
				if(mmap[j][k]=='*')pos['a'] = { j,k,-1,-1 };
			}
		}
		boxNum++;
		set<int>finded;
		cout << findBox(mmap, pos, m, n, boxNum, finded) << endl;
		
	}
	return 0;
}

发表于 2021-08-06 13:47:48 回复(0)
先计算每个宝箱到所有点的最短距离,然后从起点开始搜索
每次搜索前先遍历所有宝箱的位置,选定一个符合要求的宝箱后开始搜索,如果搜索完所有宝箱,返回步数,否则返回-1

#include<bits/stdc++.h>
using namespace std;

struct node
{
	int x,y,t;
}A[10];

char mp[55][55];
bool book[55][55];
int dp[55][55][10];//记录宝箱到每个点的最短距离 
int m,n;
int tx[4] = {0,1,0,-1};
int ty[4] = {1,0,-1,0};
int cnt;
void bfs(int x, int y, int id)//计算宝箱到每个点的最短距离 
{
	memset(book,0,sizeof(book));
	int cnt = 0;
	queue<node> q;
	node a;
	a.x = x;
	a.y = y;
	a.t = 0;
	book[x][y] = true;
	q.push(a);
	while(!q.empty())
	{
		node w = q.front();
		q.pop();
		for(int i = 0; i < 4; i++)
		{
			int xx = w.x + tx[i];
			int yy = w.y + ty[i];
			int temp = w.t+1;
			if(xx >= 1 && xx <= m && yy >= 1 && yy <= n && !book[xx][yy] && mp[xx][yy] != '#')
			{
				book[xx][yy] = true;
				dp[xx][yy][id] = temp;
				q.push(node{xx,yy,temp});
			}
		}
	}
}

int Bfs(int x, int y, int t) 
{
	node a;
	a.x = x;
	a.y = y;
	a.t = t;
	memset(book,0,sizeof(book));
	book[x][y] = 1;
	queue<node> q;
	q.push(a);
	int p = 0;
	while(!q.empty())
	{
		node w = q.front();
		q.pop();
		if(mp[w.x][w.y] >= '0' && mp[w.x][w.y] <= '9' && A[mp[w.x][w.y] - '0'].t == 0)
		{
			memset(book,0,sizeof(book));
			book[w.x][w.y] = 1;
			A[mp[w.x][w.y] - '0'].t = 1;
			p++;
		}
		if(p == cnt)
		{
			return w.t;
		}
		int maxn = 100005;
		int id;
		for(int i = 0; i < cnt; i++)
		{
			if(abs(A[i].x - w.x) + abs(A[i].y - w.y) < maxn && A[i].t == 0)
			{
				maxn = abs(A[i].x - w.x) + abs(A[i].y - w.y);
				id = i;
			}
		}
		for(int i = 0; i < 4; i++)
		{
			int xx = w.x + tx[i];
			int yy = w.y + ty[i];
			int temp = w.t+1;
			if(xx >= 1 && xx <= m && yy >= 1 && yy <= n && !book[xx][yy] && mp[xx][yy] != '#' && dp[xx][yy][id] < dp[w.x][w.y][id])
			{
				book[xx][yy] = 1;
				q.push(node{xx,yy,temp});
			}
		}
	}
	return -1;
}
int main()
{
	int t,x,y;
	cin >> t;
	while(t--)
	{
		memset(dp,0,sizeof(dp));
		cnt = 0;
		cin >> m >> n;
		cnt = 0;
		for(int i = 1; i <= m; i++)
		{
			for(int j = 1; j <= n; j++)
			{
				cin >> mp[i][j];
				if(mp[i][j] == '*')
				{
					x = i;
					y = j;
				}
				else if(mp[i][j] >= '0' && mp[i][j] <= '9')
				{
					A[mp[i][j] - '0'].x = i;
					A[mp[i][j] - '0'].y = j;
					cnt++;
				}
			}
		}
		for(int i = 0; i < cnt; i++)
		{
			bfs(A[i].x, A[i].y, i);
		}
		int ans = Bfs(x,y,0);
		cout << ans << "\n";
		for(int i = 0; i < cnt; i++)
		{
			A[i].t = 0;
			A[i].x = 0;
			A[i].y = 0;
		}
	}
} 

/*
链接:https://www.nowcoder.com/questionTerminal/1923918bf2b647deab161fd8d5d2ddfb
来源:牛客网

3
5 5
0...1
.#.#.
..*..
.#.#.
2...3
5 5
0...1
.#.#.
..*.#
.#.#.
2.#.3
5 5
....1
.####
..*..
####.
0....
*/

发表于 2021-08-07 10:58:45 回复(0)
import java.util.*;

public class Main {
    static int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};  //上下左右
    static int[][][] dis;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0){
            int m = sc.nextInt();
            int n = sc.nextInt();
            char[][] a = new char[m][n];
            int sx = 0 , sy = 0;
            Map<Integer,int[]> box = new HashMap<>();
            for(int i = 0 ; i < m ; i++){
                a[i] = sc.next().toCharArray();
                for(int j = 0 ; j < n ; j++){
                    if(a[i][j] == '*'){
                        sx = i;
                        sy = j;
                    }
                    if(a[i][j] - '0' >= 0 && a[i][j] - '0' < 10){
                        box.put(a[i][j] - '0' , new int[]{i , j});
                    }
                }
            }
            dis = new int[box.size()][m][n];    //记忆化,记录各点到各箱子的最短路径长度
            System.out.println(cntLen(a , box , sx , sy));
        }
    }

    /**
     *  模拟题目的行走方式进行移动
     *
     */
    static int cntLen(char[][] a , Map<Integer,int[]> map , int x , int y){
        int ans = 0;
        Set<String> vis = new HashSet<>();
        vis.add(x + " " + y);   //这个Set是用来记录去找一个箱子时,走过的路径的
        //如果在走到箱子之前发生路径重复,那么这里必定会形成一个循环,导致永远无法走出去
        while (map.size() > 0){
            int idx = nextBox(map , x , y); //按照题意,每次移动之后都需要根据曼哈顿距离决定下一步怎么走
            int len = dis[idx][x][y];
            int[] now = map.get(idx);
            if(len == 0){
                len = bfs(a , x , y , now[0] , now[1]); //求最短路径
                dis[idx][x][y] = len;   //记忆化
            }
            if(len == -1){  //走不过去,直接返回
                return -1;
            }
            if(len == 0){       //当前已经移动到了箱子上,移除该箱子
                vis.clear();    //整体的找箱子方式已经变化,先前路径清除
                map.remove(idx);
                continue;
            }
            for(int i = 0 ; i < 4 ; i++){
                int nx = x + dirs[i][0];
                int ny = y + dirs[i][1];
                if(nx >= 0 && nx < a.length && ny >= 0 && ny < a[0].length && a[nx][ny] != '#'){
                    if(dis[idx][nx][ny] == 0){
                        dis[idx][nx][ny] = bfs(a , nx , ny , now[0] , now[1]);
                    }
                    if(dis[idx][nx][ny] < len){ //根据题意,必须找到一个能够缩短路径的方向,并且按上下左右的顺序寻找
                        x = nx;
                        y = ny;
                        break;
                    }
                }
            }
            String now1 = x + " " + y;
            if(vis.contains(now1)){     //找到箱子前形成循环,永远无法走出去
                return -1;
            }else{
                vis.add(now1);      //记录路径
            }
            ans++;      //步数计数
        }
        return ans;
    }

    /**
     *  根据题意,每次移动都需要根据曼哈顿距离进行移动,箱子不多,直接遍历得到最近的箱子即可
     */
    static int nextBox(Map<Integer,int[]> map , int x , int y){
        int len = 10000000;
        int ans = 0;
        for(Integer num : map.keySet()){
            int[] now = map.get(num);
            int cur = Math.abs(now[0] - x) + Math.abs(now[1] - y);
            if(cur < len){
                ans = num;
                len = cur;
            }
            if(cur == len){
                ans = Math.min(ans , num);
            }
        }
        return ans;
    }

    /**
     *  简单的广度优先搜索,确定两点之间的最短路径
     */
    static int bfs(char[][] a , int sx , int sy , int tx , int ty){
        if(sx == tx && sy == ty){
            return 0;
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{sx , sy});
        int cnt = 0;
        Set<String> vis = new HashSet<>();
        vis.add(sx + " " + sy);
        while(!queue.isEmpty()){
            cnt++;
            int len = queue.size();
            for(int i = 0 ; i < len ; i++){
                int[] now = queue.poll();
                for(int j = 0 ; j < 4 ; j++){
                    int x = now[0] + dirs[j][0];
                    int y = now[1] + dirs[j][1];
                    if(x == tx && y == ty){
                        return cnt;
                    }
                    if(x >= 0 && x < a.length && y >= 0 && y < a[0].length && a[x][y] != '#' && !vis.contains(x + " " + y)){
                        queue.offer(new int[]{x , y});
                        vis.add(x + " " + y);
                    }
                }
            }
        }
        return -1;
    }
}

发表于 2021-08-20 21:35:55 回复(0)
using System;
using System.Collections;
using System.Collections.Generic;
class Program
{
   static void Main()
   {
         int T = int.Parse(Console.ReadLine());
            int[] dirX = { -1, 1, 0, 0 };
            int[] dirY = { 0, 0, -1, 1 };
            while (T-- > 0)
            {
                int[] rowcolCount = Array.ConvertAll(Console.ReadLine().Split(), Convert.ToInt32);
                int m = rowcolCount[0], n = rowcolCount[1];
                int[] nowPos = new int[2];
                string[] map = new string[m];
                int steps = 0;
                for (int i = 0; i < m; i++)
                {
                    map[i] = Console.ReadLine();
                }
                Dictionary<int, int[]> targets = new Dictionary<int, int[]>();
                for (int i = 0; i < m; i++)
                {
                    for (int j = 0; j < n; j++)
                    {
                        int number = map[i][j] - '0';
                        if (number >= 0 && number <= 9)
                        {
                            targets.Add(number, new int[2] { i, j });
                        }
                        if (map[i][j] == '*')
                        {
                            nowPos[0] = i;
                            nowPos[1] = j;
                        }
                    }
                }
                bool[,] visited = new bool[m, n];//纪录步数
                while (true)
                {
                    //获得当前目标
                    if (visited[nowPos[0], nowPos[1]])
                    {
                        Console.WriteLine(-1);
                        break;
                    }
                    visited[nowPos[0], nowPos[1]] = true;
                    int curTar = Program.GetRecent(nowPos[0], nowPos[1], targets);

                    if (curTar == -1)//这个时候宝藏已经找完了
                    {
                        Console.WriteLine(steps);
                        break;
                    }
                    int minDis = Program.GetMinDis(curTar, nowPos, targets, map);
                    if (minDis == 0)//到达宝藏
                    {
                        targets.Remove(curTar);
                        visited = new bool[m, n];
                        continue;
                    }
                    if (minDis == -1)//这个时候宝藏无法到达
                    {
                        Console.WriteLine(-1);
                        break;
                    }
                    for (int i = 0; i < 4; i++)
                    {
                        int x = nowPos[0] + dirX[i];
                        int y = nowPos[1] + dirY[i];
                        if (x >= 0 && x < m && y >= 0 && y < n
                            && map[x][y] != '#'
                            && GetMinDis(curTar, new int[2] { x, y }, targets, map) < minDis)
                        {
                            nowPos[0] = x;
                            nowPos[1] = y;
                            steps++;
                            break;
                        }
                    }
                }
            }
   }
     
       public static int GetMinDis(int target, int[] nowPos, Dictionary<int, int[]> targets, string[] map)
        {
           Queue<int[]> queue = new Queue<int[]>();
            queue.Enqueue(nowPos);
            int res = 0;
            int m = map.Length, n = map[0].Length;
            bool[,] visited = new bool[m, n];
            int[] dirX = { -1, 1, 0, 0 };
            int[] dirY = { 0, 0, -1, 1 };
            while (queue.Count > 0)
            {
                int count = queue.Count;
                for (int i = 0; i < count; i++)
                {
                    int[] cur = queue.Dequeue();
                    visited[cur[0], cur[1]] = true;
                    if (cur[0] == targets[target][0] && cur[1] == targets[target][1])
                    {
                        return res;
                    }
                    for (int j = 0; j < 4; j++)
                    {
                        int x = cur[0] + dirX[j];
                        int y = cur[1] + dirY[j];
                        if (x >= 0 && x < m && y >= 0 && y < n
                            && map[x][y] != '#'
                            && !visited[x, y]) 
                        {
                            queue.Enqueue(new int[2] { x, y });
                            visited[x, y] = true;
                        }
                    }
                }
                res++;
            }
            return -1;
        }
        //得到最近的宝藏的编号
        public static int GetRecent(int x, int y, Dictionary<int, int[]> targets)
        {
            int min = int.MaxValue;
            int res = -1;
            foreach (var item in targets)
            {
                int M = GetM(x, y, item.Value[0], item.Value[1]);
                if (M < min)
                {
                    min = M;
                    res = item.Key;
                }
                else if (M == min)
                {
                    res = Math.Min(res, item.Key);
                }
            }
            return res;
        }
        /// 得到两点间曼哈顿距离
        static int GetM(int x1, int y1, int x2, int y2)
        {
            return Math.Abs(x1 - x2) + Math.Abs(y1 - y2);
        }
}

编辑于 2022-03-19 22:03:57 回复(0)
先保留每个宝箱到地图上每个点的最短路径,然后再从起始点开始走,对走过的点进行标记,不可以走回去,只有到有宝箱的位置才将标记的点进行重置,这样就可以防止反复横跳。
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
struct node{
	int x,y,t;
}s[10];
int dp[55][55][10],n,m,cnt,vis[55][55],dy[4][2]={0,1,1,0,0,-1,-1,0};
char grid[55][55];
void BFS(int x,int y,int id){
	queue<node>q;
	memset(vis,0,sizeof(vis));
	q.push({x,y,0});
	vis[x][y]=1;
	while(!q.empty()){
		auto no = q.front();q.pop();
		for(int i=0;i<4;i++){
			int fx = no.x+dy[i][0];
			int fy = no.y+dy[i][1];
			if(fx<0||fy<0||fx>=n||fy>=m||vis[fx][fy]||grid[fx][fy]=='#')continue;
			dp[fx][fy][id]=no.t+1;
			vis[fx][fy]=1;
			q.push({fx,fy,no.t+1});
		}
	}
}
int bfs(int x,int y,int t){
	memset(vis,0,sizeof(vis));
	queue<node>q;
	q.push({x,y,0});
	vis[x][y]=1;
	int p = 0;
	while(!q.empty()){
		auto no = q.front();q.pop();
		if(grid[no.x][no.y]>='0'&&grid[no.x][no.y]<='9'&&!s[grid[no.x][no.y]-'0'].t){
			p++;
			s[grid[no.x][no.y]-'0'].t=1;
			memset(vis,0,sizeof(vis));
			vis[no.x][no.y]=1;
		}
		if(p==cnt){
			return no.t;
		}
		int maxx=INF,id;
		for(int i=0;i<cnt;i++){
			if(!s[i].t&&abs(s[i].x-no.x)+abs(s[i].y-no.y)<maxx){
				maxx = abs(s[i].x-no.x)+abs(s[i].y-no.y);
				id = i;
			}
		}
		for(int i=0;i<4;i++){
			int fx = no.x+dy[i][0];
			int fy = no.y+dy[i][1];
			if(fx<0||fy<0||fx>=n||fy>=m||vis[fx][fy]||dp[fx][fy][id]>=dp[no.x][no.y][id]||grid[fx][fy]=='#')continue;
			vis[fx][fy]=1;
			q.push({fx,fy,no.t+1});
		} 
	}
	return -1;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		cin>>n>>m;
		int x,y;
		memset(dp,0,sizeof(dp));
		cnt=0;
		for(int i=0;i<n;i++){
			cin>>grid[i];
			for(int j=0;j<m;j++){
				if(grid[i][j]=='*'){
					x=i;y=j;
				}
				else if(grid[i][j]>='0'&&grid[i][j]<='9'){
					s[grid[i][j]-'0'].x=i;
					s[grid[i][j]-'0'].y=j;
					s[grid[i][j]-'0'].t=0;
					cnt++;
				}
			}
		}
		for(int i=0;i<cnt;i++){
			BFS(s[i].x,s[i].y,i);
		}
		cout<<bfs(x,y,0)<<'\n';
	}
}


发表于 2022-06-17 19:36:22 回复(0)
int T, m, n;
class point {
public:
	int x, y, z;
	point() {};
	point(int x, int y, int z = 0) :x(x), y(y), z(z) {}
	point(const point &p):x(p.x),y(p.y),z(p.z){}
};

int walk[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};//上下左右
vector<vector<point>> way;
int bfs(vector<vector<char>>& map, point& man, point& trea) {
	way.clear();
	way.resize(m, vector<point>(n));
	vector<vector<bool>> walked(m, vector<bool>(n));
	queue<point> q;
	if (man.x == trea.x && man.y == trea.y) {
		return 0;
	}
	q.push(man);
	walked[man.x][man.y] = true;
	//cout << "bfssssssssssssssssssssssss" << endl;
	while (!q.empty()) {
		point p = q.front();
		q.pop();
		if (p.x == trea.x && p.y == trea.y) {
			//cout << "bbbbbbbbbbbbbbbbbbbbbb" << endl;
			return p.z;
		}
		for (int i = 0; i < 4; ++i) {
			int x = p.x + walk[i][0];
			int y = p.y + walk[i][1];
			int z = p.z + 1;
			if ((x >= 0 && x < m && y >= 0 && y < n) && map[x][y] != '#' && !walked[x][y]) {
				way[x][y] = p;//一个点只会从一个点走来
				q.push(point(x, y, z));//到达点(x,y)需要z步
				walked[x][y] = true;
			}
		}
		
	}
	
	return -1;
}
int mht(point& p1, vector<point>& treasure) {
	int number=0, mmin = INT16_MAX;
	for (int i = 0; i < treasure.size(); ++i) {
		if (abs(treasure[i].x - p1.x) + abs(treasure[i].y - p1.y) < mmin) {
			mmin = abs(treasure[i].x - p1.x) + abs(treasure[i].y - p1.y);
			number = i;
		}
	}
	return number;
}
//图遍历是按照上下左右次序走 1,2,3,4    false=-1 所以这里直接走最短路径
vector<point> man_way;
int check(vector<vector<char>>& map, point& man, point& trea) {
	int dis = bfs(map, man, trea);
	if (dis == -1)
		return -1;
	point p(trea.x, trea.y);
	while (!(way[p.x][p.y].x == man.x&& way[p.x][p.y].y == man.y)) {
		p = way[p.x][p.y];
	}
	man.x = p.x;
	man.y = p.y;
	for (int i = 0; i != man_way.size(); ++i) {
		if (man_way[i].x == man.x && man_way[i].y == man.y)
			return -1;
	}
	man_way.push_back(man);
	return 1;
}
int main() {
	int num;
	cin >> num;
	vector<int> s;
	while (num>0) {
		man_way.clear();
		way.clear();
		cin  >> m >> n;
		vector<point> treasure(10,point(-1,-1));
		vector<vector<char>> map(m, vector<char>(n));
		point* man=new point();
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				cin >> map[i][j];
				if (map[i][j] >='0'&&map[i][j] <= '9') {
					treasure[map[i][j] - '0'] = point(i, j);
				}
				else if (map[i][j] == '*') {
					man = new point(i, j);
					man_way.push_back(*man);
				}
			}
		}
		int steps = 0;
		for (auto i=treasure.end()-1;i!=treasure.begin();) {
			if ((*i).x == -1) {
				--i;
				treasure.pop_back();
			}
			else break;
		}
		while (treasure.size()!=0)
		{
			//cout << "wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww" << endl;
			int k = mht(*man, treasure);
			int step = check(map, *man, treasure[k]);
			if (step == -1) {
				steps = -1;
				break;
				//return 0;
			}
			++steps;
			if (man->x == treasure[k].x && man->y == treasure[k].y) {
				//cout << steps <<"  :"<< map[(*(treasure.begin() + k)).x][(*(treasure.begin() + k)).y]
				//	<<"("<< (*(treasure.begin() + k)).x<<","<< (*(treasure.begin() + k)).y<< endl;
				treasure.erase(treasure.begin() + k);
				man_way.clear();
				
			}
		}
		s.push_back(steps);
		--num;
	}
	for (int x : s) {
		cout << x << endl;
	}
	return 0;
}

发表于 2022-03-17 10:15:37 回复(0)
好困难的模拟题......首先要会用BFS寻找最短路径,其次按照这个最短路径一步一步的走,不断更新各个宝箱的曼哈顿距离。如果发现有其它宝箱的曼哈顿距离比当前的更小,要更换目标宝箱,重新生成最短路径。当宝箱全部找到后结束循环。
按照题目例子3中所说,可能出现反复横跳的情况。于是定义一个visited数组,判断某个点是否走过。只有当找到一个宝箱后,这个visited数组才重置。
#include <bits/stdc++.h>
using namespace std;

typedef struct point{
    int x, y;
    int front;  //路径前一个位置下标
    int dir;    //上一个位置走哪个方向到达此位置 0,1,2,3 ~ 上下左右
    point(int _x = 0, int _y = 0, int _no = -1):x(_x), y(_y), no(_no), front(-1){}

    point operator+(const point& ano){
        return point(x + ano.x, y + ano.y);
    }
    bool operator==(const point& ano){
        return x == ano.x && y == ano.y;
    }

    int no; //宝箱编号
    int md; //曼哈顿距离
    static bool cmp(const point& p1, const point& p2){
        if( p1.md != p2.md )
            return p1.md < p2.md;
        else
            return p1.no < p2.no;
    }
}Point;

Point dir[4] {Point(-1, 0), Point(1, 0), Point(0, -1), Point(0, 1)};
vector<vector<char>> maze;
int T, m, n;

bool pointLegal(int x, int y, vector<vector<int>>& flag)
{
    return  (x>=0 && x<m) && (y>=0 && y<n) && (flag[x][y]==0)
        && (maze[x][y]=='.' || maze[x][y]=='*' || isdigit(maze[x][y]));
}

bool findPath(Point start, Point end, vector<Point>& path)
{
    vector<vector<int>> flag(m, vector<int>(n, 0));
    Point que[2000];
    que[0] = start;

    for(int i = 0, cnt = 1; i < cnt; ++i){
        if( que[i] == end ){
            Point p = que[i];
            while( p.front != -1 ){
                path.emplace_back(p);
                p = que[p.front];
            }
            return true;
        }
        for(int k = 0; k < 4; ++k){
            Point p = que[i] + dir[k];
            if( pointLegal(p.x, p.y, flag) ){
                flag[p.x][p.y] = 1;
                p.front = i;
                p.dir = k;
                que[cnt++] = p;
            }
        }
    }
    return false;
}

//  更新曼哈顿距离
bool updateMd(const Point& player, vector<Point>& treasure)
{
    Point firstT = treasure[0];
    for(auto& p : treasure)
        p.md = abs(player.x - p.x) + abs(player.y - p.y);
    sort(treasure.begin(), treasure.end(), Point::cmp);

    return firstT == treasure[0];   //判断宝物目标有没有改变
}

int main()
{
    
    cin >> T;
    while( T-- )
    {
        cin >> m >> n;
        vector<vector<char>>(m, vector<char>(n)).swap(maze);

        Point player;
        vector<Point> path;
        vector<Point> treasure;
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                cin >> maze[i][j];
                if( maze[i][j] == '*' ){
                    player.x = i;
                    player.y = j;
                }else if( isdigit(maze[i][j]) )
                    treasure.emplace_back( Point(i, j, maze[i][j]-'0') );
            }
        }
        
        // for(int i = 0; i < m; ++i){
        //     for(int j = 0; j < n; ++j)
        //         printf("%c ", maze[i][j]);
        //     putchar('\n');
        // }
        // putchar('\n');
        
        int  len = 0;
        bool canFind = true;
        vector<vector<int>> visited(m, vector<int>(n, 0));
        visited[player.x][player.y] = 1;

        vector<Point> totalPath;
        while( treasure.size() > 0 )
        {
            bool notChangeTarget = updateMd(player, treasure);
            //  需要更换路径:第一次进入 或 有其它宝箱曼哈顿距离更小
            if( (path.size() == 0) || (!notChangeTarget) ){
                // cout << "target is " << treasure[0].no << endl;
                path.clear();
                if( !findPath(player, treasure[0], path) ){
                    canFind = false;
                    break;
                }
            }
            // cout << path.size() << endl;
            // cout << "(" << player.x << ", " << player.y << "), direction is " << path.rbegin()->dir << endl;
            player = player + dir[path.rbegin()->dir];
            // cout << "now come to (" << player.x << ", " << player.y << ")\n";

            totalPath.emplace_back(player);
            if( visited[player.x][player.y] == 1 ){
                canFind = false;
                break;
            }
            visited[player.x][player.y] = 1;
            if( player == treasure[0] ){
                treasure.erase(treasure.begin());
                vector<vector<int>>(m, vector<int>(n, 0)).swap(visited);
            }

            path.pop_back();
            len++;
        }
        printf("%d\n", canFind ? len : -1);
    }
    return 0;
}


发表于 2021-08-06 03:20:28 回复(0)
注意每次移动之后都要重新判断目标箱子。
仅当当前遇到了宝箱,才删除一个目标箱子
从题目示例中可以看到,可能出现反复横跳的情况。
可以简单保存visited数组,记录遇到过的状态。
这里可以简单的用(剩下的宝箱数量,当前位置)来记录。
剩下的就是广度优先搜索,找到最短路径长度。
按照题目要求一步步模拟。
发表于 2021-06-05 16:53:02 回复(0)