Knights of Ni S

链接

这题感觉就是常规bfs,我们只需把贝茜的路分成两段即可

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
struct location {
	int x=0, y=0;
};
int a[4] = { -1,0,1,0 };
int b[4] = { 0,1,0,-1 };
void search(int x,int y,vector<vector<int>>&Map, vector<vector<int>>&foot,int n,int m) {
	queue<location>q;
	q.push({ x,y });
	while (!q.empty()) {
		location cur = q.front();
		q.pop();
		for (int i = 0;i< 4;i++) {
			int x1 = cur.x + a[i], y1 = cur.y + b[i];
			if (0 <= x1 && x1 < n && 0 <= y1 && y1 < m) {
				if (Map[x1][y1] == 0 || Map[x1][y1] == 4) {
					if (foot[cur.x][cur.y] + 1 < foot[x1][y1]) {
						foot[x1][y1] = foot[cur.x][cur.y] + 1;
						q.push({ x1,y1 });
					}
				}
			}
		}
	}
}

void back(int x, int y, vector<vector<int>>& Map, vector<vector<int>>& foot, int n, int m) {
	queue<location>q;
	q.push({ x,y });
	while (!q.empty()) {
		location cur = q.front();
		q.pop();
		for (int i = 0;i< 4;i++) {
			int x1 = cur.x + a[i], y1 = cur.y + b[i];
			if (0 <= x1 && x1 < n && 0 <= y1 && y1 < m) {
				if (Map[x1][y1] == 0 || Map[x1][y1] == 4||Map[x1][y1]==2) {
					if (foot[cur.x][cur.y] + 1 < foot[x1][y1]) {
						foot[x1][y1] = foot[cur.x][cur.y] + 1;
						q.push({ x1,y1 });
					}
				}
			}
		}
	}
}

int main() {
	int m, n;
	cin >> m >> n;
	vector<vector<int>>Map(n, vector<int>(m));
	vector<vector<int>>foot1(n, vector<int>(m,233333));
	vector<vector<int>>foot2(n, vector<int>(m, 233333));
	location start, end;
	vector<location>wood;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			cin >> Map[i][j];
			if (Map[i][j] == 2) {
				start.x = i, start.y = j;
			}
			else if (Map[i][j] == 3) {
				end.x = i, end.y = j;
			}
			else if (Map[i][j] == 4) {
				wood.push_back({ i,j });
			}
		}
	}

	foot1[start.x][start.y] = 0;
	foot2[end.x][end.y] = 0;

	search(start.x, start.y, Map, foot1, n, m);
	//search(end.x, end.y, Map, foot2, n, m);
	back(end.x, end.y, Map, foot2, n, m);

	int result = 233333;
	for (auto it : wood) {
		result = min(foot1[it.x][it.y] + foot2[it.x][it.y], result);
	}
	cout << result << endl;
	/*for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			cout << foot1[i][j] << " ";
		}
		cout << endl;
	}
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			cout << foot2[i][j] << " ";
		}
		cout << endl;
	}*/
}

注释是我的测试,不用管

时间复杂度:O(mn)

空间复杂度:O(nm)