[USACO07OCT] Obstacle Course S

链接

这个也是搜索问题,我们考虑四个方向, 设置一个三维数组arr[105][105][5] 当最后一个为0代表地图('.','x','A','B')

其他情况分别是西北东南

设置方向数组保证方向正确

为防止无限递归,我们需要剪枝(找到最小情况即可,大了就剪枝)

代码如下

#include<iostream>
#include<string>
#include<memory>
using namespace std;
pair<int, int>start, End;
int n;
int arr[105][105][5];
int a[5] = { 0,0,-1,0,1 };
int b[5] = { 0,-1,0,1,0 };
//W N E S
void bfs(int x,int y,int dir) {

	if (x == End.first && y == End.second) {
		return;
	}
	

	//直走
	int x1 = x + a[dir];
	int y1 = y + b[dir];
	if (arr[x1][y1][0] != 'x') {
		if (0 <= x1 && x1 < n && 0 <= y1 && y1 < n) {
			if (arr[x1][y1][dir] > arr[x][y][dir] && arr[x1][y1][dir] != -10) {
				arr[x1][y1][dir] = arr[x][y][dir];
				bfs(x1, y1, dir);
			}
			else if (arr[x1][y1][dir] == -10) {
				arr[x1][y1][dir] = arr[x][y][dir];
				bfs(x1, y1, dir);
			}
		}
	}

	//左转
	int l_dir = dir - 1 == 0 ? 4 : dir - 1;
	if (arr[x][y][l_dir] !=-10 ) {
		if (arr[x][y][dir] + 1 < arr[x][y][l_dir]) {
			arr[x][y][l_dir] = arr[x][y][dir] + 1;
			bfs(x, y, l_dir);

		}
		
	}
	else {
		arr[x][y][l_dir] = arr[x][y][dir] + 1;
		bfs(x, y, l_dir);

	}
	
	//右转

	int r_dir = dir + 1 == 5 ? 1 : dir + 1;
	if (arr[x][y][r_dir] != -10) {
		if (arr[x][y][dir] + 1 < arr[x][y][r_dir]) {
			arr[x][y][r_dir] = arr[x][y][dir] + 1;
			bfs(x, y, r_dir);
		}
	}
	else {
		arr[x][y][r_dir] = arr[x][y][dir] + 1;
		bfs(x, y, r_dir);
	}
	
}
int main() {
	int dire = 1;
	int t = 4;
	int count = 2e9;
	cin >> n;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			char st;
			cin >> st;
			arr[i][j][0] = st;
			if (arr[i][j][0] == 'A') {
				start.first = i;
				start.second = j;
			}
			else if (arr[i][j][0] == 'B') {
				End.first = i;
				End.second = j;
			}
		}
	}
	while (t--) {
		for (int i = 0;i < n;i++) {
			for (int j = 0;j < n;j++) {
				for (int k = 1;k < 5;k++) {
					arr[i][j][k] = -10;
				}
			}
		}
		
		
		
		arr[start.first][start.second][dire] = 0;
		bfs(start.first, start.second, dire);//由于初始方向不确定,我们就所有情况都试一遍
		dire++;
		for (int j = 1;j < 5;j++) {
			if (arr[End.first][End.second][j] == -10) continue;
			count = min(count, arr[End.first][End.second][j]);
		}
	}
	if (count == 2e9) {
		cout << -1;
	}
	else {
		cout << count;
	}

}

时间复杂度:O(4n²)

空间复杂度:O(n²)