寫在前面：

? ? ? ? 最近還是想著找專題提升一下自己，嘗試來寫kuangbin專題，每天更新一點，希望可以更完

?

1、棋盤問題

? ? ? 用 ban ，visr，visl三個數組記錄那些位置可以被訪問，然后dfs搜索即可

? ?

#include <iostream> #include <cstdio> #include <cstring> using namespace std; typedef long long LL; typedef pair<int,int> Pi; typedef unsigned long long ULL; int gcd(int a,int b){if (b == 0) return a; return gcd(b , a%b);} int lcm(int a, int b){ return a/gcd(a,b)*b;} inline int read(){int f = 1, x = 0;char ch = getchar();while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f; } const int maxn = 105; int visr[maxn],visl[maxn]; int ban[maxn][maxn]; int ans,n,k,tot; char s[maxn][maxn]; void init(){memset(visr, 0, sizeof(visr));memset(visl, 0, sizeof(visl));memset(ban, 0, sizeof(ban));ans = 0; } void dfs(int x,int y){//cout << x << ' ' << y << ' ' << k << endl;if (k == 0) {ans++; return;}if (x > n || y > n) return;if (!visr[x] && !visl[y] && !ban[x][y]){visr[x] = visl[y] = 1; k--;if (y == n) dfs(x+1, 1);else dfs(x, y+1);visr[x] = visl[y] = 0; k++;}if (y == n) dfs(x+1, 1);else dfs(x, y+1); } int main(){//freopen("/Users/chutong/data.txt", "r", stdin);while (scanf("%d%d",&n,&k) == 2) {if (n == -1 && k == -1) break; init();for (int i=1; i<=n; i++){scanf("%s",s[i]+1);for (int j=1; j<=n; j++) {if (s[i][j] == '.') ban[i][j] = 1;else tot++;}}dfs(1, 1);printf("%d\n",ans);}return 0; }

?

2、Dungeon Master

? ? ? 這是一個三維的搜索問題，在二維平面的基礎上，加一個軸，模版不變，判出界，判節點能否訪問（bfs比較好，dfs需要剪枝不然太慢）

#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; typedef long long LL; typedef unsigned long long ULL; int Gcd(int a,int b){if (b == 0) return a; return Gcd(b , a%b);} int Lcm(int a, int b){ return a/Gcd(a,b)*b;} inline int read(){int f = 1, x = 0;char ch = getchar();while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f; } const int N = 50; char mp[N][N][N]; int vis[N][N][N]; int dx[N] = {-1,1,0,0,0,0}; int dy[N] = {0,0,1,-1,0,0}; int dz[N] = {0,0,0,0,-1,1}; int L,R,C; struct Point{int x,y,z;int step; }; bool check(int x,int y,int z){if (x < 1 || x > R || y < 1 || y > C || z < 1 || z > L) return false;return true; } int bfs(int sx,int sy,int sz){queue<Point> q;q.push((Point){sx,sy,sz,0});while(!q.empty()){Point now = q.front(); q.pop();if (mp[now.z][now.x][now.y] == 'E') return now.step;for(int i=0; i<6; i++){int x = now.x+dx[i],y = now.y+dy[i],z = now.z+dz[i];if (!vis[z][x][y] && mp[z][x][y] != '#' && check(x,y,z)){vis[z][x][y] = 1;q.push((Point){x,y,z,now.step+1});}}}return -1; } // mp[z][x][y]; int main(){// freopen("/Users/chutong/ACM/data.in","r",stdin);while(scanf("%d%d%d",&L,&R,&C) && (L != 0 || R != 0 || C != 0)){memset(vis,0,sizeof(vis));memset(mp,0,sizeof(mp));int sx = 0,sy = 0,sz = 0;for(int i=1; i<=L; i++){for(int j=1; j<=R; j++){scanf("%s",mp[i][j]+1);for(int k=1; k<=C; k++){if (mp[i][j][k] == 'S'){sx = j; sy = k; sz = i;}}}}int ans = bfs(sx,sy,sz);if (ans == -1) printf("Trapped!\n");else printf("Escaped in %d minute(s).\n",ans);}return 0; }

?

3、Catch That Cow

? ? ? 后期再嘗試下搜索，這題可以轉化為圖論，i 和?i+1 兩個節點建邊權為 1，i 和 i*2 建邊，最后跑一遍最短路即可（dij單源）

#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; typedef long long LL; typedef pair<int,int> Pi; typedef unsigned long long ULL; int Gcd(int a,int b){if (b == 0) return a; return Gcd(b , a%b);} int Lcm(int a, int b){ return a/Gcd(a,b)*b;} inline int read(){int f = 1, x = 0;char ch = getchar();while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f; } const int maxn = 2e6 + 10; int head[maxn],tot; int dis[maxn]; struct _edge{int to,nex,w; }edge[maxn]; void add(int u,int v,int w){edge[tot] = (_edge){v,head[u],w};head[u] = tot++; } void init(){memset(head,-1,sizeof(head)); } void dij(int s,int dis[]){for(int i=0; i<maxn; i++) dis[i] = 1e9; dis[s] = 0;priority_queue<Pi,vector<Pi>,greater<Pi> > pq; pq.push(make_pair(dis[s],s));while(!pq.empty()){Pi now = pq.top(); pq.pop();int u = now.second;for(int i=head[u];~i; i=edge[i].nex){int v = edge[i].to;if (dis[v] > dis[u] + edge[i].w){dis[v] = dis[u] + edge[i].w;pq.push(make_pair(dis[v],v));}}} } int main(){int n = read(),k = read(); init();for(int i=0; i<=1e5; i++){add(i,i+1,1); add(i,i-1,1); }for(int j=0; j<=1e5; j++){add(j,j*2,1);}dij(n,dis);cout << dis[k] << endl;return 0; }

?

總結

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

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