6.4.2 走迷宮

利用bfs尋找最短路。通過對u/m得到x，u%m得到y(tǒng)。u = x * m + y
將方向保存在dx[], dy[]中。

c
int q[maxn*maxn]; void bfs(int x, int y) {int front = 0, rear = 0, d, u;u = x*m + y;vis[x][y] = 1; fa[x][y] = u; dist[x][y] = 0;q[rear++] = u;while(front < rear){u = q[front++];x = u/m; y = u %m;for(d = 0; d < 4; d++){int nx = x + dx[d], ny = y + dy[d];if (nx >= 0 && nx < n && ny >= 0 && ny <m && maze[nx][ny] && !vis[nx][ny]){int v= nx * m + ny;q[rear++] = v;vis[nx][ny] = 1;fa[nx][ny] = u;dist[nx][ny] = dist[x][y]+1;last_dir[nx][ny] = d;}}} }

6.4.3 拓撲排序，DAG（Directed Acyclic Graph)有向無環(huán)圖

c#include <stdio.h> #include <string.h>const int maxn = 1000; const int maxm = 1000;// 用于判斷是否存在環(huán) int c[maxn]; int topo[maxn], t; int n, m; int G[maxm][maxm];bool dfs(int u) {c[u] = -1;for(int v= 0; v < n; v++) if(G[u][v]){if(c[v] < 0) return false;else if(!c[v] && !dfs(v)) return false;}c[u] = 1; topo[--t] = u;return true; }bool toposort() {t = n;memset(c, 0, sizeof(c));for(int u = 0; u < n; u++) if(!c[u])if(!dfs(u)) return false;return true; }int main() {int u, v;while(~scanf("%d %d", &n, &m)){memset(G, 0, sizeof(G));memset(topo, 0, sizeof(topo));for(int i = 0; i < m; i++){scanf("%d %d", &u, &v);G[u][v] = 1;}if(toposort()){for(int i = 0; i < n; i++)printf("%d ", topo[i]);printf("\n");} else {printf("sort error\n");}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的ACM - 第6章 数据结构基础（2）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。