專題1 簡單搜索

點擊題目名稱可以直接跳轉

棋盤問題

類似八皇后

#include <iostream> #include <cstring>using namespace std;const int N = 10;int n, k; char g[N][N]; bool col[N];//當前列是否擺放棋子 int ans;//方案數量//當前要去搜索第u行，已經放了t個棋子 void dfs(int u, int t) {if(t == k)//當前擺放棋子數量達到要求，方案數+1{ans ++;return ;}if(n - u < k - t) return ;//剩余可以擺放棋子的行數小于剩余棋子數量if(u == n) return ;//所有行搜索完畢dfs(u + 1, t);//當前行不放棋子，直接搜索下一行for(int i = 0; i < n; i ++)//循環當前行每一列if(g[u][i] == '#' && !col[i])//可以放并且該列沒放過{col[i] = true;dfs(u + 1, t + 1);col[i] = false;} }int main() {while(cin >> n >> k && n != -1){for(int i = 0; i < n; i ++) cin >> g[i];//兩個初始化ans = 0; memset(col, 0, sizeof col);dfs(0, 0);cout << ans << endl; }return 0; }

Dungeon Master

常規廣搜題，不難就是有點麻煩

#include <iostream> #include <cstring>using namespace std;const int N = 35, M = N * N * N;char g[N][N][N]; int L, R, C; int x1, x2, y1, y2, z1, z2; bool st[N][N][N]; int d[N][N][N]; int dx[] = {0, 0, 0, 0, -1, 1}, dy[] = {0, 0, -1, 1, 0, 0}, dz[] = {1, -1, 0, 0, 0, 0}; struct location {int x, y, z; };void bfs() {location q[M], r;int hh = 0, tt = 0;//手寫隊列 // q[0] = {x1, y1, z1};估計是POJ沒跟上時代，不支持c++新特性r.x = x1, r.y = y1, r.z = z1;//按照老的來吧q[0] = r;d[x1][y1][z1] = 0;st[x1][y1][z1] = true;while(hh <= tt){location t = q[hh ++];int a = t.x, b = t.y, c = t.z;for(int i = 0; i < 6; i ++){int tx = a + dx[i], ty = b + dy[i], tz = c + dz[i];if(tx < 1 || tx > R || ty < 1 || ty > C || tz < 1 || tz > L) continue;if(g[tx][ty][tz] == '#' || st[tx][ty][tz]) continue;location k;k.x = tx, k.y = ty, k.z = tz;q[++ tt] = k;st[tx][ty][tz] = true;d[tx][ty][tz] = d[a][b][c] + 1;if(tx == x2 && ty == y2 && tz == z2) return ;}} }int main() {while(cin >> L >> R >> C && L){for(int k = 1; k <= L; k ++){for(int i = 1; i <= R; i ++){for(int j = 1; j <= C; j ++){cin >> g[i][j][k];if(g[i][j][k] == 'S') x1 = i, y1 = j, z1 = k;if(g[i][j][k] == 'E') x2 = i, y2 = j, z2 = k;}// getchar();這里不用讀空格也可以} // getchar();}//每次搜索前來個初始化memset(d, 0, sizeof d), memset(st, 0, sizeof st); bfs();if(d[x2][y2][z2] == 0) puts("Trapped!");else printf("Escaped in %d minute(s).\n", d[x2][y2][z2]);//別忘了這里最后還有個'.'}return 0; }

Catch That Cow

#include <iostream> #include <queue>using namespace std;const int N = 1e5 + 10;int n, k; int d[N];int bfs() {queue<int> q;q.push(n);while(q.size()){int t = q.front();q.pop();if(t == k) return d[k];//往左走if(t - 1 >= 0 && !d[t - 1]) q.push(t - 1), d[t - 1] = d[t] + 1;//一旦走到k點了就沒必要再往右走了if(t + 1 <= k && !d[t + 1]) q.push(t + 1), d[t + 1] = d[t] + 1;if(t * 2 <= k + 1 && !d[t * 2]) q.push(t * 2), d[t * 2] = d[t] + 1;//路徑翻倍的時候最多只需要跳到k+1，如果跳到>k+1的地方比如說k+2//那我們還需要往回跳兩次，總共需要三次//但是我們完全可以一開始不跳兩倍的距離直接向右跳一步，然后再讓距離翻倍//這樣只需要兩步足矣} }int main() {cin >> n >> k;cout << bfs();return 0; }

Fliptile

每次觸碰一個方格的時候會改變上下左右和自己，用最少的次數將所有方格變成0

本題和 費解的開關 如出一轍，不同的是本題要輸出方案而不是方案個數， 費解的開關一題收錄在基礎篇當中

#include <iostream> #include <cstring>using namespace std;const int N = 20;int n, m; int g[N][N], back[N][N]; int res[N][N], tmp[N][N]; int dx[] = {0, -1, 0, 1, 0}, dy[] = {0, 0, 1, 0, -1}; int ans = 1e9;void turn(int x, int y) {for(int i = 0; i < 5; i ++){int a = x + dx[i], b = y + dy[i];if(a >= 0 && a < n && b >= 0 && b < m)g[a][b] ^= 1;} }void work() {for(int i = 0; i < (1 << m); i ++){memcpy(g, back, sizeof back);memset(tmp, 0, sizeof tmp);int cnt = 0;for(int j = 0; j < m; j ++)if(i >> j & 1){turn(0, m - j - 1);cnt ++;tmp[0][m - j - 1] = 1;}for(int j = 0; j < n - 1; j ++)for(int k = 0; k < m; k ++)if(g[j][k] == 1){turn(j + 1, k);cnt ++;tmp[j + 1][k] = 1;}bool f = true;for(int j = 0; j < m; j ++)if(g[n - 1][j] == 1){f = false;break;}if(!f) continue;if(cnt < ans){ans = cnt;memcpy(res, tmp, sizeof tmp);}}if(ans == 1e9) puts("IMPOSSIBLE");else{for(int i = 0; i < n; i ++){for(int j = 0; j < m; j ++)cout << res[i][j] << ' ';cout << endl;}} }int main() {cin >> n >> m;for(int i = 0; i < n; i ++)for(int j = 0; j < m; j ++){scanf("%d", &g[i][j]);back[i][j] = g[i][j];}work();return 0; }

本題核心在于二進制暴力枚舉，暴力枚舉就等同于暴力搜索

Find The Multiple

題目雖然說m是不超過200位的十進制數，但是對于所有的n <= 200，我們都能在long long范圍內(2^63-1)內找到解，所以我們就按m是在LL范圍內來做就行了，不用搞那么復雜，當爆LL以后我們就停止搜索

#include <iostream>using namespace std;typedef long long LL;int n;bool dfs(LL ans, int digit) {if(digit > 19) return false;//LL最多19位if(ans % n == 0) {cout << ans << endl;return true;}if(dfs(ans * 10, digit + 1)) return true;if(dfs(ans * 10 + 1, digit + 1)) return true; }int main() {while(cin >> n && n){dfs(1, 1);}return 0; }

這道題不推薦用BFS來寫，大概率會T，如果你一定要寫BFS，記得也提交一下G++，那個可能不會T

總結

以上是生活随笔為你收集整理的kuangbin专题 专题1 简单搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。