## BFS 从初态S，利用规则生成所有可能的状态，构成下一层节点，检查是否出现目标状态G 若未出现，对该层再次生成、检查，直到出现目标节点 1. 将初始节点添加到队列Q 2. if Q的第一个节点q是目标节点，Then 停止 3. 从Q中删除q，把q的尚未访问的子节点加入Q的末尾 4. if Q为空 Then 失败，Else goto 步骤2 [例题：POJ3984](https://vjudge.net/contest/701114#problem/A) ```cpp #include #include using namespace std; int mp[5][5], vis[5][5]; int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; struct node{ int x, y; }; node pre[10][10]; void bfs(){ queue que; node str; str.x = str.y = 0; que.push(str); vis[0][0] = 1; while (!que.empty()){ node now = que.front(); que.pop(); if (now.x == 4 && now.y == 4) return; for (int i = 0; i < 4; i++){ node next ; next.x = now.x + dir[i][0]; next.y = now.y + dir[i][1]; if (next.x >= 0 && next.x < 5 && next.y >= 0 && next.y < 5 && !mp[next.x][next.y] && !vis[next.x][next.y]){ vis[next.x][next.y] = 1; que.push(next); pre[next.x][next.y] = now; } } } } void print(node cur){ if (cur.x == 0 && cur.y == 0){ printf("(0, 0)\n"); return; } print(pre[cur.x][cur.y]); printf("(%d, %d)\n", cur.x, cur.y); } int main(){ for (int i = 0; i < 5; i++) for (int j = 0; j < 5; j++) scanf("%d", &mp[i][j]); bfs(); node ed; ed.x = ed.y = 4; print(ed); return 0; } ``` [例题：POJ1915](https://vjudge.net/contest/701114#problem/B) ```cpp #include #include #include using namespace std; int length, sx, dx, sy, dy; struct node{ int x, y, step; }; int visit[310][310]; int po[8][2] = {2, 1, 2, -1, 1, 2, 1, -2, -2, 1, -2, -1, -1, 2, -1, -2}; int check(int x, int y){ if (x < 0 || x >= length || y < 0 || y >= length) return 1; return visit[x][y]; } void bfs(){ memset(visit, 0, sizeof(visit)); node a, b; queue Q; a.x = sx; a.y = sy; a.step = 0; visit[sx][sy] = 1; Q.push(a); while (!Q.empty()){ a = Q.front(); Q.pop(); if (a.x == dx && a.y == dy){ printf("%d\n", a.step); return; } for (int i = 0; i < 8; i++){ b.x = a.x + po[i][0]; b.y = a.y + po[i][1]; if (check(b.x, b.y)) continue; b.step = a.step + 1; visit[b.x][b.y] = 1; Q.push(b); } } } int main(){ int T; scanf("%d", &T); while (T--){ scanf("%d", &length); scanf("%d%d%d%d", &sx, &sy, &dx, &dy); bfs(); } return 0; } ``` ## DFS 对每一个可能的分支深入到不能再转移为止，然后回溯到前一步的状态，继续转移到前一步的状态，直到找到最终的解 1. 把起始点放入stack 2. 重复下述3步骤，直到stack为空为止： - 从stack中访问栈顶的点 - 找出与此点邻接的且尚未遍历的点，进行标记，然后全部放入stack中 - 如果此点没有尚未遍历的邻接点，则将此点从stack中弹出。 [例题：POJ2386](https://vjudge.net/contest/701114#problem/C) ```cpp #include using namespace std; int N, M; const int MAX_N = 103; char field[MAX_N][MAX_N]; void dfs(int x, int y){ field[x][y] = '.'; for (int dx = -1; dx <= 1; dx++){ for (int dy = -1; dy <= 1; dy++){ int nx = x + dx, ny = y + dy; if (0 <= nx && nx < N && 0 <= ny && ny < M && field[nx][ny] == 'W') dfs(nx, ny); } } return; } void solve(){ int res = 0; for (int i = 0; i < N; i++){ for (int j = 0; j < M; j++){ if (field[i][j] == 'W'){ dfs(i, j); res++; } } } cout << res; } int main(){ cin >> N >> M; for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) cin >> field[i][j]; solve(); } ``` [例题：POJ2488](https://vjudge.net/contest/701114#problem/D) ```cpp #include #include #include using namespace std; const int DN = 8; const int dx[] = {-1, 1, -2, 2, -2, 2, -1, 1}; const int dy[] = {-2, -2, -1, -1, 1, 1, 2, 2}; const int N = 27; bool visit[N][N]; struct Step{ char x, y; } path[N]; int p, q, success; void dfs(int x, int y, int step){ path[step].y = y + 'A' - 1; path[step].x = x + '0'; if (step == p * q) success = true; else { for (int i = 0; i < DN && !success; i++){ int nx = x + dx[i]; int ny = y + dy[i]; if (0 < nx && nx <= p && 0 < ny && ny <= q && !visit[nx][ny] && !success){ visit[nx][ny] = true; dfs(nx, ny, step + 1); visit[nx][ny] = false; } } } } int main(){ int t; scanf("%d", &t); for (int k = 1; k <= t; k++){ scanf("%d%d", &p, &q); memset(visit, false, sizeof(visit)); visit[1][1] = true; success = false; dfs(1, 1, 1); printf("Scenario #%d:\n", k); if (success){ for (int i = 1; i <= p * q; i++) printf("%c%c", path[i].y, path[i].x); printf("\n"); } else printf("impossible\n"); if (k != t) printf("\n"); } return 0; } ```

Schabe Antimonfeld

ACM-ICPC基础 搜索算法的解空间

ACM-ICPC基础搜索算法的解空间