【算法1-7】搜索【持续更新中】

题目链接：P1219 [USACO1.5]八皇后 Checker Challenge - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 

#include 
using namespace std;
int n, cnt;

int a[50], b[50], c[50], d[50]; //行 列 主对角线 次对角线
void dfs(int i) {
	if (i > n) {
		if (cnt <= 2) {
			for (int k = 1; k <= n; k++) {
				cout << a[k] << ' ';
			}
			cout << endl;
		}
		cnt++;
		return;
	}
	for (int j = 1; j <= n; j++) {
		if (b[j] == 0 && c[i - j + n] == 0 && d[i + j] == 0) {
			a[i] = j;
			b[j] = 1;
			c[i - j + n] = 1;
			d[i + j] = 1;
			dfs(i + 1);
			b[j] = 0;
			c[i - j + n] = 0;
			d[i + j] = 0;
		}
	}
}

int main() {
	cin >> n;
	dfs(1);
	cout << cnt;
	return 0;
}

题目链接：P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include 
#include 
#include 
#include 
using namespace std;

int xx[8] = {1, 1, 2, 2, -1, -1, -2, -2};

int yy[8] = {-2, 2, -1, 1, -2, 2, -1, 1};
queue>q;
int s[410][410];
bool flag[410][410];

int main() {
	int n, m, x, y;
	memset(s, -1, sizeof(s));
	cin >> n >> m >> x >> y;
	flag[x][y] = 1;
	s[x][y] = 0;
	q.push(make_pair(x, y));
	while (!q.empty()) {
		int a = q.front().first, b = q.front().second;
		q.pop();
		for (int i = 0; i < 8; i++) {
			int aa = a + xx[i], bb = b + yy[i];
			if (aa > n || bb > m || aa < 1 || bb < 1 || flag[aa][bb]) {
				continue;
			}
			flag[aa][bb] = 1;
			q.push(make_pair(aa, bb));
			s[aa][bb] = s[a][b] + 1;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << left << setw(5) << s[i][j];
		}
		cout << endl;
	}
	return 0;
}

题目链接：P1135 奇怪的电梯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include 
#include 
using namespace std;

class floor {
	public:
		int no;//楼层号
		int cnt;//到达这层需要的次数
};
queueq;

int c[500];//记录每层楼上的数字
bool flag[500];//记录每层楼是否被访问
int main() {
	int n, a, b;
	cin >> n >> a >> b;
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
	}
	floor f, f2;
	f.no = a;
	f.cnt = 0;
	flag[a] = 1;
	q.push(f);
	while (!q.empty()) {
		f2 = q.front();
		q.pop();
		if (b == f2.no) {
			break;
		}
		int t = f2.no + c[f2.no];
		if (t <= n && flag[t] == 0) {
			f.no = t;
			f.cnt = f2.cnt + 1;
			q.push(f);
			flag[t] = 1;
		}
		t = f2.no - c[f2.no];
		if (t >= 1 && flag[t] == 0) {
			f.no = t;
			f.cnt = f2.cnt + 1;
			q.push(f);
			flag[t] = 1;
		}
	}
	if (f2.no == b) {
		cout << f2.cnt;
	} else {
		cout << -1;
	}
	return 0;
}

题目链接：P2895 [USACO08FEB]Meteor Shower S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include 
#include 
using namespace std;
int a[310][310];//记录陨石砸落的最早时间点 下标是坐标
int b[310][310];//记录到达每个点的最早时间
bool flag[310][310];//记录每个点是否被走过
queue>q;

int dx[5] = {0, 0, 0, 1, -1};

int dy[5] = {0, 1, -1, 0, 0};

int main() {
	int n, x, y, t;
	cin >> n;
	for (int i = 0; i < 310; i++) {
		for (int j = 0; j < 310; j++) {
			a[i][j] = -1; //初始化
		}
	}
	for (int i = 0; i < n; i++) {
		cin >> x >> y >> t;
		for (int j = 0; j < 5; j++) { //妙哇
			if (x + dx[j] >= 0 && y + dy[j] >= 0 && (a[x + dx[j]][y + dy[j]] == -1
			        || a[x + dx[j]][y + dy[j]] > t)) { //合法坐标且没被砸过或者被砸得更早需要更新时间点
				a[x + dx[j]][y + dy[j]] = t;
			}
		}
	}
	flag[0][0] = 1;
	q.push(make_pair(0, 0));
	while (!q.empty()) {
		int xx = q.front().first;
		int yy = q.front().second;
		q.pop();
		if (a[xx][yy] == -1) {
			cout << b[xx][yy];
			return 0;
		}
		for (int i = 1; i <= 4; i++) {
			int xxx = xx + dx[i];
			int yyy = yy + dy[i];
			if (xxx >= 0 && yyy >= 0 && (a[xxx][yyy] > b[xx][yy] + 1 || a[xxx][yyy] == -1)
			        && flag[xxx][yyy] == 0) { //是合法坐标且到达该点的时间早于陨石砸到该点的时间且该点未被访问过
				q.push(make_pair(xxx, yyy));
				flag[xxx][yyy] = 1;
				b[xxx][yyy] = b[xx][yy] + 1;
			}
		}
	}
	cout << -1;
	return 0;
}