2025年大一ACM訓練-搜索

前期知識：DFS，本文搜索題解法以深度優先搜索為主
1.1 DFS 的定義
深度優先搜索（Depth-First Search）是一種用于遍歷樹或圖的算法。核心思想是盡可能“深入”訪問圖的每個節點，直到無法繼續前進為止，然后再回溯到之前的節點繼續遍歷。

1.2 DFS 的工作原理
DFS 的基本步驟如下：

1. 訪問當前節點：從起點節點開始訪問。
2. 遞歸遍歷子節點：依次訪問當前節點的所有未被訪問過的子節點。
3. 回溯：當所有子節點都被訪問完畢后，回溯到父節點繼續遍歷。

1.3 DFS 的典型應用場景
迷宮求解：尋找從起點到終點的路徑。
連通性問題：判斷圖中的兩個節點是否連通。
路徑查找：在圖中查找從一個節點到另一個節點的所有可能路徑。
DFS主要以棧結構或遞歸來實現，遞歸本質上也是棧結構的運用

讀者可通過以下視頻進行初步學習

Problem A 迷宮尋路-搜索：

#include<bits/stdc++.h>
using namespace std;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char a[1001][1001];
int posx[2],posy[2],n,m;
void dfs(int x,int y)
{a[x][y]='#';int x1,y1,i;for(i=0;i<4;i++){x1=x+dir[i][0];y1=y+dir[i][1];if(x1>=0 && x1<n && y1>=0 && y1<m && a[x1][y1]=='*'){dfs(x1,y1);}}
}
int main()
{int i,j;while(cin>>n>>m){int p=-1;for(i=0;i<n;i++){for(j=0;j<m;j++){cin>>a[i][j];if((i==0 || i==n-1 || j==0 || j==m-1) &&a[i][j]=='*'){posx[++p]=i;posy[p]=j;}}}dfs(posx[0],posy[0]);if(a[posx[1]][posy[1]]=='#') cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}

從代碼里可以看出幾個關鍵部分：
①對于迷宮問題，對開始點和結束點的確定是必要部分
②在dfs函數內(x,y)點要朝上下左右四個方向移動，用dir數組來實現簡化
③判斷邊界
④對于已經訪問過的節點要標記，防止陷入死循環

Problem B 白與黑-搜索：

#include <bits/stdc++.h>
using namespace std;int graph[21][21];
int w, h, startX, startY, cnt = 0;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
void dfs(int x, int y)
{graph[x][y] = 0;cnt++;for (int i = 0; i < 4; i++){int nx = x + dx[i];int ny = y + dy[i];if (nx >= 1 && nx <= w && ny >= 1 && ny <= h && graph[nx][ny] == 1){dfs(nx, ny);}}
}int main() {while (cin >> w >> h && w && h){memset(graph, 0, sizeof(graph));cnt = 0;for (int i = 1; i <= h; i++) {for (int j = 1; j <= w; j++) {char ch;cin >> ch;if (ch == '#') graph[j][i] = 0;else if (ch == '.') graph[j][i] = 1;else if (ch == '@') {startX = j;startY = i;graph[j][i] = 1;}}}dfs(startX, startY);cout << cnt << endl;}return 0;
}

Problem C 搜索入門-搜索:

#include<bits/stdc++.h>
using namespace std;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char a[5][5];
void dfs(int x,int y)
{a[x][y]='*';int x1,y1,i;for(i=0;i<4;i++){x1=x+dir[i][0];y1=y+dir[i][1];if(x1>=0 && x1<4 && y1>=0 && y1<4 && a[x1][y1]=='#'){dfs(x1,y1);}}
}
int main()
{int n,i,j;cin>>n;while(n--){for(i=0;i<4;i++)for(j=0;j<4;j++) cin>>a[i][j];dfs(0,0);if(a[3][3]=='*') cout<<"YES"<<endl;else cout<<"NO"<<endl;}
}

Problem D 逃出迷宮-搜索:

這題和其他幾個有所不同，用的是BFS，具體不在本文闡述

#include<bits/stdc++.h>
#define MAX_R 1000
#define MAX_C 1000
#define INF INT_MAX
typedef struct {int x, y;int time;
} Position;
typedef struct {int x, y;
} Fire;
char maze[MAX_R][MAX_C];
int dist[MAX_R][MAX_C];
int fire_dist[MAX_R][MAX_C];
Position queue[MAX_R * MAX_C];
Fire fire_queue[MAX_R * MAX_C];
int front,rear,fire_front,fire_rear,R,C;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
void bfs_fire()
{fire_front=fire_rear=0;for (int i=0;i<R;i++){for (int j=0;j<C;j++){if (maze[i][j]=='F'){fire_queue[fire_rear].x=i;fire_queue[fire_rear].y=j;fire_rear++;fire_dist[i][j] = 0;}else fire_dist[i][j] = INF;}}while (fire_front<fire_rear){Fire current=fire_queue[fire_front];fire_front++;for (int i=0;i<4;i++){int nx = current.x + dx[i];int ny = current.y + dy[i];if (nx >= 0 && nx < R && ny >= 0 && ny < C && maze[nx][ny] != '#' && fire_dist[nx][ny] == INF) {fire_dist[nx][ny] = fire_dist[current.x][current.y] + 1;fire_queue[fire_rear].x = nx;fire_queue[fire_rear].y = ny;fire_rear++;}}}
}
int bfs_joe() {int start_x = -1, start_y = -1;for (int i = 0; i < R; i++){for (int j = 0; j < C; j++){if (maze[i][j] == 'J'){start_x = i;start_y = j;break;}}if (start_x != -1) break;}front = rear = 0;queue[rear].x = start_x;queue[rear].y = start_y;queue[rear].time = 0;rear++;dist[start_x][start_y] = 0;while (front < rear){Position current = queue[front];front++;for (int i = 0; i < 4; i++){int nx = current.x + dx[i];int ny = current.y + dy[i];if (nx < 0 || nx >= R || ny < 0 || ny >= C)return current.time + 1;if (nx >= 0 && nx < R && ny >= 0 && ny < C && maze[nx][ny] != '#' && dist[nx][ny] == -1 && (current.time + 1 < fire_dist[nx][ny] || fire_dist[nx][ny] == INF)){dist[nx][ny] = current.time + 1;queue[rear].x = nx;queue[rear].y = ny;queue[rear].time = current.time + 1;rear++;}}}return -1;
}
int main()
{int T;cin>>T:while (T--){cin>>R>>C;for (int i=0;i<R;i++) cin>>maze[i];bfs_fire();memset(dist, -1, sizeof(dist));int result = bfs_joe();if (result == -1) cout<<"IMPOSSIBLE"<<endl;else cout<<result<<endl;}return 0;
}

Problem E 林大超市買水果-搜索:

#include<bits/stdc++.h>
using namespace std;
int M, N, K;
int prices[31];
bool found = false;
void dfs(int start,int count,int sum)
{if (found) return;if (count == K){if (sum == M){found = true;}return;}for (int i=start;i<N;i++){if (sum+prices[i]>M) continue;dfs(i+1,count+1,sum+prices[i]);}
}
int main()
{cin>>M>>N>>K;for (int i = 0; i < N; i++)cin>>prices[i];dfs(0,0,0);if (found) printf("Yes\n");else printf("No\n");return 0;
}

Problem F 瓷磚-搜索:

#include <bits/stdc++.h>
using namespace std;int graph[51][51];
int w, h, startX, startY, cnt = 0;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
void dfs(int x, int y)
{graph[x][y] = 0;cnt++;for (int i = 0; i < 4; i++){int nx = x + dx[i];int ny = y + dy[i];if (nx >= 1 && nx <= w && ny >= 1 && ny <= h && graph[nx][ny] == 1){dfs(nx, ny);}}
}int main()
{while (cin >> w >> h && w && h){memset(graph, 0, sizeof(graph));cnt = 0;for (int i = 1; i <= h; i++) {for (int j = 1; j <= w; j++) {char ch;cin >> ch;if (ch == '#') graph[j][i] = 0;else if (ch == '.') graph[j][i] = 1;else if (ch == '@'){startX = j;startY = i;graph[j][i] = 1;}}}dfs(startX,startY);cout<<cnt<<endl;}return 0;
}

Problem G 最大黑色區域-搜索:

#include<bits/stdc++.h> 
using namespace std;
int n,m,ans=1,mmax;
char mapc[105][105];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x0, int y0)
{for (int i=0;i<4;i++){int x =x0+dir[i][0];int y =y0+dir[i][1];if (mapc[x][y] == '1'){mapc[x][y] = '0';ans++;dfs(x, y);}}
}int main()
{cin>>n>>m;for (int i=1;i<=n;i++){for (int j=1;j<=m;j++)cin>>mapc[i][j];}for (int i=1;i<=n;i++){for (int j=1;j<=m;j++){if (mapc[i][j] == '1'){mapc[i][j]='0';dfs(i,j);mmax=max(mmax,ans);ans = 1;}}}cout << mmax << endl;return 0;
}

Problem H 猴群-搜索:

#include<bits/stdc++.h> 
using namespace std;
int n, m, ans = 0;
char mapc[105][105];
int dir[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};void dfs(int x, int y)
{for (int i = 0; i < 4; i++){int nx = x + dir[i][0];int ny = y + dir[i][1];if (nx>=1 && nx<=n && ny>=1 && ny<=m && mapc[nx][ny]!='0'){mapc[nx][ny] = '0';dfs(nx,ny);}}
}int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++)cin >> mapc[i][j];}for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (mapc[i][j] != '0'){ans++;dfs(i,j);}}}cout << ans<<endl;return 0;
}

總體來說除D題是BFS算法，E題不是迷宮問題，其余均是基本的DFS迷宮題型，代碼容易且相似。