搜索（DFS和BFS）

深搜是我最早学的算法，当然现在还没有信手拈来就是了。。。

为了更好地学树和图，只能回来刷搜索了。。。。。我已经搜了一天了啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊（疯癫）

首先是今天去刷的八皇后问题，特别经典的搜索题，我记得我有一天深夜学算法就看了这个八皇后问题，其实深搜和广搜没有什么模板，就是纯暴力然后标记然后再暴力再标记。。。

调试调试应该没大问题，，，吧。

附上今天八皇后代码：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<queue>
 4 #include<cmath>
 5 #include<set>
 6 #include<vector>
 7 using namespace std;
 8 #define int long long
 9 #define endl '\n'
10 const int N = 1e3 + 10, inf = 0x3f3f3f3f3f3f3f3f;
11 int a[N], rr[N], cc[N], rc[N], cr[N];
12 int ans, n;
13 void print() {
14     if (ans <= 3) {
15         for (int i = 1; i <= n; i++)
16             cout << a[i] << " ";
17         cout << endl;
18     }
19 }
20 bool check(int r, int c) {
21     if (rr[r] || cc[c] || rc[r + c] || cr[r - c + n])return false;
22     rr[r] = 1; cc[c] = 1; rc[r + c] = 1; cr[r - c + n] = 1;
23     return true;
24 }
25 void cancel(int r, int c) {
26     rr[r] = 0; cc[c] = 0; rc[r + c] = 0; cr[r - c + n] = 0;
27 }
28 void dfs(int x) {
29     for (int i = 1; i <= n; i++) {
30         if (check(x, i)) {
31             a[x] = i;
32             if (x == n) {
33                 ans++;
34                 print();
35                 cancel(x, i);
36                 return;
37             }
38             dfs(x + 1);
39             cancel(x, i);
40         }
41     }
42 }
43 void solve() {
44     cin >> n;
45     dfs(1);
46     cout << ans;
47 }
48 signed main() {
49     ios::sync_with_stdio(false);
50     cin.tie(0);
51     cout.tie(0);
52     int t = 1;
53     //cin >> t;
54     while (t--) solve();
55     return 0;
56 }

一开始在check函数中我用的是stl中的set中的find来标记各种情况，但是最后t了，logn的时间复杂度不过如此。。。

后来发现可以直接用数组，，，我真蠢啊啊啊啊啊啊啊啊啊啊啊啊啊。。。

接下来是bfs，一开始这道我是用dfs做的，结果，样例都过不了，后来自习观察了一下，发现是一道bfs。。。我是真的菜。。。。

马的遍历，上代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define int long long
 4 #define endl '\n'
 5 const int N = 1e3 + 10, inf = 0x3f3f3f3f3f3f3f3f;
 6 int a[N][N], nextt[8][2] = { {2,1},{-2,1},{-2,-1},{2,-1},{1,2},{1,-2},{-1,-2},{-1,2} };
 7 bool book[N][N];
 8 void bfs(int n,int m,int x,int y) {
 9     queue<pair<int,int>> q;
10     q.push(make_pair(x,y));
11     while (!q.empty()) {
12         x = q.front().first, y = q.front().second;
13         q.pop();
14         for (int i = 0; i < 8; i++) {
15             int tx = x + nextt[i][0], ty = y + nextt[i][1];
16             if (book[tx][ty] || tx > n || ty > m || tx < 1 || ty < 1)continue;
17             book[tx][ty] = true;
18             a[tx][ty] = a[x][y] + 1;
19             q.push(make_pair(tx, ty));
20         }
21     }
22 }
23 void solve() {
24     int n, m, x, y;
25     cin >> n >> m >> x >> y;
26     memset(a, -1, sizeof(a));
27     memset(book, false, sizeof(book));
28     book[x][y] = true;
29     a[x][y] = 0;
30     bfs(n,m,x,y);
31     for (int i = 1; i <= n; i++) {
32         for (int j = 1; j <= m; j++)
33             cout << a[i][j] << " ";
34         cout << endl;
35     }
36 }
37 signed main() {
38     ios::sync_with_stdio(false);
39     cin.tie(0);
40     cout.tie(0);
41     int t = 1;
42     //cin >> t;
43     while (t--) solve();
44     return 0;
45 }

突然发现bfs的代码和dijkstra的优先队列法有点一样？？？所以dijkstra是用bfs哦！！！！！！！！！！！！我个sb，写了那么久bfs，现在才发现那是bfs。。。