深搜是我最早学的算法，当然现在还没有信手拈来就是了。。。
为了更好地学树和图，只能回来刷搜索了。。。。。我已经搜了一天了啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊（疯癫）
首先是今天去刷的八皇后问题，特别经典的搜索题，我记得我有一天深夜学算法就看了这个八皇后问题，其实深搜和广搜没有什么模板，就是纯暴力然后标记然后再暴力再标记。。。
调试调试应该没大问题，，，吧。
附上今天八皇后代码：
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。。。