[搜索]奥特曼打怪兽

题目描述

奥特曼是正义的化身,现在奥特曼需要消灭地图中所有怪鲁,该地图由一个M×M的矩阵组成,地图中的怪兽有不同的难度级别。
0表示陷阱,不能进入
1表示陆地,可以通过
大于等于2的正整数表示各种级别的怪兽,数字越大表示怪兽越强。
现在奥特曼需要按照级别从弱到强消灭地图中所有的怪兽,怪兽一旦被消灭,怪兽所在的地方就变回为陆地。
奥特曼从原地开始(0,0)行动,在地图中只能上下左右移动,那么奥特曼最少需要走多少步才能消灭所有怪兽, 如果无法消灭所有怪曽返回-1。
约束:
1.地图中不会有级别一样的怪兽
2.不允许宾特曼经过一个怪兽而不消灭它
输入描述:
一个由M×M构成的炬阵,3≤M≤50,该矩阵每行数字之间用空格隔开
输出描述:
如果奥特曼能够依次消灭所有怪兽,输出最小步数,如果无法全部消灭输出-1。

输入样例

1 2 0
0 3 4
0 6 5

输出样例

5

思路描述

乍一看,是到搜索题。

等我跑步回来写……

方法一:BFS

#include <bits/stdc++.h>
using namespace std;
class Point{
public:
	int i, j;
	int num;
	Point(int i, int j, int num) {
		this->i = i;
		this->j = j;
		this->num = num;
	}
	Point() {}
	bool operator < (const Point& p) const {
		return num < p.num;
	}
};
int main() {
    freopen("./1.input.txt","r",stdin);
	vector<Point> points;
	Point temp;
	while (cin >> temp.num) {
		points.push_back(temp);
	}
	int m = sqrt(points.size());
	vector<vector<int>> matrix(m, vector<int>(m, 0));
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			matrix[i][j] = points[i * m + j].num;
			points[i * m + j].i = i;
			points[i * m + j].j = j;
		}
	}
	sort(points.begin(), points.end());
	temp.num = 1;
	int index = upper_bound(points.begin(), points.end(), temp) - points.begin();
	if (index == points.size()) {
		printf("0\n");
	} else {
		int dir[][2] = { 0, 1, 0, -1, 1, 0, -1, 0 };
		int res = 0;
		Point curPoint{ 0, 0, 0 };
		for (int pIndex = index; pIndex < points.size(); pIndex++) {
			Point &nextPoint = points[pIndex];
			matrix[nextPoint.i][nextPoint.j] = 1;
			queue<Point> que;
			que.push(curPoint);
			vector<vector<bool>> isVis(m, vector<bool>(m, false));
			bool isFind = false;
			while (!que.empty()) {
				Point p = que.front();
				que.pop();
				if (p.i == nextPoint.i && p.j == nextPoint.j) {
					res += p.num;
					isFind = true;
					break;
				}
				for (int i = 0; i < 4; i++) {
					int ii = p.i + dir[i][0];
					int jj = p.j + dir[i][1];
					if (ii >= 0 && ii < matrix.size() && jj >= 0 && jj < matrix[0].size()
						&& matrix[ii][jj] == 1 && isVis[ii][jj] == false) {
						isVis[ii][jj] = true;
						que.push({ ii, jj, p.num + 1 });
					}
				}
			}
			if (isFind == false) {
				res = -1;
				break;
			}
			curPoint.i = nextPoint.i;
			curPoint.j = nextPoint.j;
		}
		printf("%d\n", res);
	}
	return 0;
}

方法二:DFS

#include <bits/stdc++.h>
using namespace std;
class Point {
public:
    int i, j;
    int num;
    Point() {}
    Point(int i, int j, int num) {
        this->i = i;
        this->j = j;
        this->num = num;
    }
    bool operator < (const Point& p) const {
        return num < p.num;
    }
};
const int X[4] = {0, 0, 1, -1};
const int Y[4] = {1, -1, 0, 0};
vector<vector<int> > c;
int m;
void dfs(Point& in, Point& out, int v, int& minv,  vector<vector<bool> >& vis) {
    if(in.i == out.i && in.j == out.j) {
        if(v < minv) {
            minv = v;
            return;
        }
    }
    vis[in.i][in.j] = true;
    for(int i=0; i<4; i++) {
        int ni = in.i + X[i];
        int nj = in.j + Y[i];
        if (ni>=0 && nj>=0 && ni<m && nj<m && c[ni][nj]==1 && !vis[ni][nj]) {
            Point next;
            next.i = ni, next.j = nj;
            next.num = in.num + 1;
            dfs(next, out, v+1, minv, vis);
        }
    }
    vis[in.i][in.j] = false;
}
int main(void) {
    freopen("./1.input.txt","r",stdin);
    vector<Point> points;
    Point tmp;
    const int M = 55;
    char l[M];
    int i=0, j=0;
    while(fgets(l,M,stdin)!=NULL) {
        j = 0;
        char *p = strtok(l, " ");
        vector<int> tp;
        while(p) {
            int t = stoi(p);
            tp.push_back(t);
            tmp.i = i, tmp.j = j, tmp.num = t;;
            points.push_back(tmp);
            p = strtok(NULL, " ");
            j++;
        }
        c.push_back(tp);
        i++;
    }
    m = c.size();
    int total = 0;
    int MAX = 1<<30;
    sort(points.begin(), points.end());
    tmp.num = 1;
    int index = upper_bound(points.begin(), points.end(), tmp) - points.begin();
    if (index == points.size()) {
        printf("0\n");
    } else {
        Point curPoint{ 0, 0, 0 };
        for (int pIndex = index; pIndex < points.size(); pIndex++) {
            Point &nextPoint = points[pIndex];
            c[nextPoint.i][nextPoint.j] = 1;
            vector<vector<bool> > vis(m, vector<bool>(m, false));
            int res = MAX;
            dfs(curPoint, nextPoint, 0, res, vis);
            if(res == -1 || res == MAX) {
                printf("-1\n");
                return 0;
            } else {
                total += res;
            }
            curPoint = nextPoint;
        }
    }
    printf("%d\n", total);
    return 0;
}

测试输入用例(不全)

1 2 0
0 3 4
0 6 7
1 2 0
0 3 4
8 0 0
1 2 5 0
0 3 4 1
0 8 0 6
0 0 0 7

总结

  • 无论是BFS还是DFS都不适用于地图变化的情形,所以要转换为地图不变的问题来处理。比如,明确“起点”、“终点”。
  • 明确好“岔道口”和“死胡同”在题目中的指代,即可转换为搜索问题。当然这道题还算明显。