小白書上經(jīng)典DFS題目。

1. 遞歸實(shí)現(xiàn)

// from: https://www.cnblogs.com/huaszjh/p/4686092.html#include <stdio.h> #include <string.h> #define maxn 105 unsigned char data[maxn][maxn]; int m, n, vis[maxn][maxn];void dfs(int x, int y, int ans) {if (x < 0 || x >= m || y < 0 || y >= n) return; //出界if (vis[x][y] > 0 || data[x][y] == '*') return; //非'@'或已經(jīng)訪問vis[x][y] = ans; //連通分量編號for (int k = -1; k <= 1; k++) {for (int t = -1; t <= 1; t++) {if (k != 0 || t != 0) { //自身格子不需要重復(fù)判斷dfs(x + k, y + t, ans);}}} }#define DEBUG int main() { #ifdef DEBUGconst char* input_txt_pth = "F:/zhangzhuo/debug/OJ/UVA-572.txt";freopen(input_txt_pth, "r", stdin); #endifint i, j;while (scanf("%d %d", &m, &n) && m &&n) {int count = 0; //連通塊memset(vis, 0, sizeof(vis));for (i = 0; i < m; i++) {scanf("%s", data[i]);}for (i = 0; i < m; i++) {for (j = 0; j < n; j++) {//對未訪問且為`@`的格子進(jìn)行訪問if (vis[i][j] == 0 && data[i][j] == '@') {dfs(i, j, ++count);}}}printf("%d\n", count); #ifdef DEBUGfor (i = 0; i < m; i++) {for (j = 0; j < n; j++) {printf("%3d", vis[i][j]);}printf("\n");}printf("\n"); #endif}return 0; }

2. 遞歸dfs函數(shù)用迭代實(shí)現(xiàn)
每個節(jié)點(diǎn)的dfs遞歸調(diào)用，改成用stack容器就地計(jì)算，是個while循環(huán)，本質(zhì)上還是棧，但是避免了遞歸時嵌套產(chǎn)生的開銷造成的潛在風(fēng)險。

C++的stack、vector容器用起來比較順手。另外就是把坐標(biāo)簡單封裝為一個結(jié)構(gòu)體。

#include <stdio.h> #include <string.h> #include <iostream> #include <stack> #include <vector>typedef struct Coord {char x, y; } Coord;#define DEBUG int main() { #ifdef DEBUGconst char* input_txt_pth = "F:/zhangzhuo/debug/OJ/UVA-572.txt";freopen(input_txt_pth, "r", stdin); #endifint m, n, i, j;#define maxn 105unsigned char data[maxn][maxn];int vis[maxn][maxn];while (scanf("%d %d", &m, &n) && m &&n) {int count = 0; //連通塊memset(vis, 0, sizeof(vis));for (i = 0; i < m; i++) {scanf("%s", data[i]);}std::stack<Coord> stk;Coord cd;std::vector<Coord>offset;cd.x = -1; cd.y = -1; offset.push_back(cd);cd.x = -1; cd.y = 0; offset.push_back(cd);cd.x = -1; cd.y = 1; offset.push_back(cd);cd.x = 0; cd.y = -1; offset.push_back(cd);cd.x = 0; cd.y = 1; offset.push_back(cd);cd.x = 1; cd.y = -1; offset.push_back(cd);cd.x = 1; cd.y = 0; offset.push_back(cd);cd.x = 1; cd.y = 1; offset.push_back(cd);for (i = 0; i < m; i++) {for (j = 0; j < n; j++) {cd.x = i; cd.y = j;if (vis[cd.x][cd.y] > 0 || data[cd.x][cd.y] != '@') continue;count++;stk.push(cd);while (!stk.empty()) {cd = stk.top();stk.pop();vis[cd.x][cd.y] = count;Coord tmp;for (size_t k = 0; k < offset.size(); k++) {tmp.x = cd.x + offset[k].x;tmp.y = cd.y + offset[k].y;if (tmp.x < 0 || tmp.x >= m || tmp.y < 0 || tmp.y >= n) continue;if (vis[tmp.x][tmp.y] > 0 || data[tmp.x][tmp.y] != '@') continue;stk.push(tmp);}}}}printf("%d\n", count);#ifdef DEBUGfor (i = 0; i < m; i++) {for (j = 0; j < n; j++) {printf("%3d", vis[i][j]);}printf("\n");}printf("\n"); #endif}return 0; }

3.純C，DFS非遞歸，自定義棧ADT，函數(shù)指針

#include <stdio.h> #include <string.h> #include <stdlib.h> #include <string.h>typedef struct Coord Coord; struct Coord {char x, y; };typedef struct CoordOffset CoordOffset; struct CoordOffset {size_t num;int* x;int* y; };typedef struct ListNode ListNode; struct ListNode {ListNode* next;void* data; };typedef struct Stack Stack;struct Stack {ListNode* head;size_t len;void(*push_coord)(Stack* stk, Coord* coord);void (*pop_coord)(Stack* stk);void (*top_coord)(Stack* stk, Coord* coord); };void stack_push_coord(Stack* stk, Coord* coord) {ListNode* new_head = (ListNode*)malloc(sizeof(ListNode));/* new_head->data = coord; */new_head->data = (Coord*)malloc(sizeof(ListNode));memcpy(new_head->data, coord, sizeof(Coord));new_head->next = stk->head;stk->head = new_head;stk->len++; }void stack_pop_coord(Stack* stk) {if (stk->head != NULL) {ListNode* new_head = stk->head->next;free(stk->head->data);free(stk->head);stk->head = new_head;stk->len--;} }void stack_top_coord(Stack* stk, Coord* coord) {if (stk->head != NULL) {Coord* t_coord = (Coord*)(stk->head->data);coord->x = t_coord->x;coord->y = t_coord->y;} }void make_stack(Stack** _stk) {Stack* stk = (Stack*)malloc(sizeof(Stack));stk->head = NULL;stk->len = 0;stk->push_coord = stack_push_coord;stk->pop_coord = stack_pop_coord;stk->top_coord = stack_top_coord;/* write back */*_stk = stk; }void free_stack(Stack* stk) {ListNode* cur = stk->head;ListNode* temp;size_t i;for (i = 0; i < stk->len; i++) {temp = cur->next;free(cur->data);free(cur);cur = temp;}free(stk);stk = NULL; }void make_8coord_offset(CoordOffset** _offset) {CoordOffset* offset = (CoordOffset*)malloc(sizeof(CoordOffset));offset->num = 8;offset->x = (int*)malloc(sizeof(int)*offset->num);offset->y = (int*)malloc(sizeof(int)*offset->num);offset->x[0] = -1; offset->y[0] = -1;offset->x[1] = -1; offset->y[1] = 0;offset->x[2] = -1; offset->y[2] = 1;offset->x[3] = 0; offset->y[3] = -1;offset->x[4] = 0; offset->y[4] = 1;offset->x[5] = 1; offset->y[5] = -1;offset->x[6] = 1; offset->y[6] = 0;offset->x[7] = 1; offset->y[7] = 1;/* write back */*_offset = offset; }void free_coord_offset(CoordOffset* offset) {if (offset) {if (offset->x) {free(offset->x);offset->x = NULL;}if (offset->y) {free(offset->y);offset->y = NULL;}free(offset);offset = NULL;} }/* #define DEBUG */ int main() { #ifdef DEBUGconst char* input_txt_pth = "F:/zhangzhuo/debug/OJ/UVA-572.txt";freopen(input_txt_pth, "r", stdin); #endifint m, n, i, j;size_t k;#define maxn 105unsigned char data[maxn][maxn];int vis[maxn][maxn];/* here we use 8 neighbours */CoordOffset* offset = NULL;make_8coord_offset(&offset);while (scanf("%d %d", &m, &n) && m &&n) {int count = 0; /* 連通塊 */memset(vis, 0, sizeof(vis));for (i = 0; i < m; i++) {scanf("%s", data[i]);}/* std::stack<Coord> stk; */Stack* stk;make_stack(&stk);Coord cd;for (i = 0; i < m; i++) {for (j = 0; j < n; j++) {cd.x = i; cd.y = j;if (vis[cd.x][cd.y] > 0 || data[cd.x][cd.y] != '@') continue;count++;/* stk.push(cd); */stack_push_coord(stk, &cd);/* while (!stk.empty()) { */while(stk->len!=0) {/* cd = stk.top(); *//* stack_top_coord(stk, &cd); */stk->top_coord(stk, &cd);/* stk.pop(); *//* stack_pop_coord(stk); */stk->pop_coord(stk);vis[cd.x][cd.y] = count;Coord tmp;for (k = 0; k < offset->num; k++) {tmp.x = cd.x + offset->x[k];tmp.y = cd.y + offset->y[k];if (tmp.x < 0 || tmp.x >= m || tmp.y < 0 || tmp.y >= n) continue;if (vis[tmp.x][tmp.y] > 0 || data[tmp.x][tmp.y] != '@') continue;/* stk.push(tmp); *//* stack_push_coord(stk, &tmp); */stk->push_coord(stk, &tmp);}}}}free_stack(stk);printf("%d\n", count);#ifdef DEBUGfor (i = 0; i < m; i++) {for (j = 0; j < n; j++) {printf("%3d", vis[i][j]);}printf("\n");}printf("\n"); #endif}free_coord_offset(offset);return 0; }

4.DFS+并查集實(shí)現(xiàn)

#include <stdio.h> #include <stdio.h> #include <string.h> #include <stdlib.h>int fa[10500]; int m, n, cnt, vis[105][105]; char mp[105][105]; int find(int x) {if (fa[x] == x) return x;fa[x] = find(fa[x]);return fa[x]; }void merge(int x, int y) {int fx = find(x);int fy = find(y);if (fx == fy) return;fa[fx] = fy; }void dfs(int x, int y, int fx, int fy) {if (x < 0 || x >= m || y < 0 || y >= n) return;if (vis[x][y] || mp[x][y] == '*') return;vis[x][y] = 1;/* cout<<"x || y || fx || fy : "<<x<<" || "<<y<<" || "<<fx<<" || "<<fy<<endl; */if (fx != -1) {merge(x*m + y, fx*m + fy);}int i, j;for (i = -1; i < 2; i++) {for (j = -1; j < 2; j++) {if (!i && !j) continue;dfs(x + i, y + j, x, y);}} }/* #define LOCAL */ int main() { #ifdef LOCALconst char* input_txt = "F:/zhangzhuo/debug/OJ/UVA-572.txt";freopen(input_txt, "r", stdin); #endifint i, j;while (scanf("%d%d", &m, &n) == 2 && m && n) {cnt = 0;memset(vis, 0, sizeof(vis));for (i = 0; i < m; i++) {scanf("%s", mp[i]);}for (i = 0; i < 10500; i++) {fa[i] = i;}for (i = 0; i < m; i++) {for (j = 0; j < n; j++) {if (!vis[i][j] && mp[i][j] == '@') {dfs(i, j, -1, -1);cnt++;}}}printf("%d\n", cnt);#ifdef LOCALfor (i = 0; i < m; i++) {for (j = 0; j < n; j++) {printf("%3d", vis[i][j]);}printf("\n");}printf("\n"); #endif}return 0; }

5.DFS+并查集+不使用全局變量+簡單封裝為結(jié)構(gòu)體
修改自 UVA572 (并查集解法) 。這種寫法有點(diǎn)問題：已經(jīng)用了dfs，dfs里用并查集多此一舉，如果用并查集就不應(yīng)該遞歸調(diào)用dfs。

#include <stdio.h> #include <stdio.h> #include <string.h> #include <stdlib.h>typedef struct FSU_Node {int p; /* parent id */int rank;int vis; /* group(connected component) id */ } FSU_Node;/* get node's root id @param x: node id @param nodes: all nodes in map */ int fus_find(int x, FSU_Node* nodes) {if (nodes[x].p == x) return x;nodes[x].p = fus_find(nodes[x].p, nodes);return nodes[x].p; }/* merge two node groups @param a: a node from one node group @param b: a node from another node group */ void fus_union(int a, int b, FSU_Node* nodes) {int ra = fus_find(a, nodes); /* ra: root id of a */int rb = fus_find(b, nodes); /* rb: root id of b */if (ra == rb) {return;}if (nodes[ra].rank > nodes[rb].rank){nodes[rb].p = ra;}else {if (nodes[ra].rank == nodes[rb].rank){nodes[rb].rank++;}nodes[ra].p = rb;} }typedef struct ImageSize {int w, h; } ImageSize;typedef struct Coord {int row, col; } Coord;void fus_dfs(const Coord* pt, const Coord* f_pt, FSU_Node* nodes, ImageSize* sz, unsigned char* mp) {int row = pt->row;int col = pt->col;int f_row = f_pt->row;int f_col = f_pt->col;if (row < 0 || row >= sz->h || col < 0 || col >= sz->w) return;int id = row * sz->w + col;int fid = f_row * sz->w + f_col;/* if (vis[id] || mp[id] == '*') return; */if (nodes[id].vis || mp[id] == '*') return;/* vis[id] = 1; */nodes[id].vis = 1;if (f_row != -1) {fus_union(id, fid, nodes);}int i, j;Coord neighbor;for (i = -1; i < 2; i++) {for (j = -1; j < 2; j++) {if (!i && !j) continue;neighbor.row = row + i;neighbor.col = col + j;fus_dfs(&neighbor, pt, nodes, sz, mp);}} }/*#define LOCAL*/ int main() { #ifdef LOCALconst char* input_txt = "F:/zhangzhuo/debug/OJ/UVA-572.txt";freopen(input_txt, "r", stdin); #endif#define MAXN 105int m, n, cnt, i, j;/* int vis[MAXN*MAXN]; */unsigned char mp[MAXN*MAXN];FSU_Node nodes[MAXN*MAXN];int idx;while (scanf("%d%d", &m, &n) == 2 && m && n) {cnt = 0;/* memset(vis, 0, sizeof(int)*MAXN*MAXN); */for (i = 0; i < m; i++) {for (j = 0; j < n; j++) {idx = i * n + j;scanf(" %c", &mp[idx]);/* printf("! %c !", mp[idx]); */}}for (i = 0; i < m*n; i++) {nodes[i].p = idx;nodes[i].rank = 1;nodes[i].vis = 0;}ImageSize im_sz;im_sz.h = m;im_sz.w = n;Coord pt;Coord f_pt;f_pt.row = -1;f_pt.col = -1;for (i = 0; i < m; i++) {for (j = 0; j < n; j++) {idx = i * n + j;/* if (!vis[idx] && mp[idx] == '@') { */if (!nodes[idx].vis && mp[idx] == '@') {/* dfs(i, j, -1, -1); */pt.row = i;pt.col = j;/* fus_dfs(&pt, &f_pt, nodes, &im_sz, vis, mp); */fus_dfs(&pt, &f_pt, nodes, &im_sz, mp);cnt++;}}}printf("%d\n", cnt);#ifdef LOCALfor (i = 0; i < m; i++) {for (j = 0; j < n; j++) {idx = i * m + j;/* printf("%3d", vis[idx]); */printf("%c", mp[idx]);}printf("\n");}printf("\n"); #endif}return 0; }

這里的教訓(xùn)是，如果在雙重for循環(huán)中使用變量x、y來表示坐標(biāo)，容易把2維度坐標(biāo)->1維坐標(biāo)的計(jì)算算錯。使用row,col能減少犯錯可能；
另外就是數(shù)據(jù)讀取，這里改成%c，則需要過濾掉換行符\n，方法是scanf時的格式串首部添加空格：scanf(" %c", &xx)

6. 并查集，去掉了DFS
思路：遍歷每個像素點(diǎn)，每個像素點(diǎn)用并查集算法合并周邊8鄰域中為'@'的像素點(diǎn)。再次遍歷，統(tǒng)計(jì)每個'@'像素對應(yīng)的等價類（root節(jié)點(diǎn)）的值。第三次遍歷，把第二次統(tǒng)計(jì)的值當(dāng)中cnt數(shù)大于0的累計(jì)，就是區(qū)域個數(shù)。在統(tǒng)計(jì)連通域個數(shù)的時候順帶把每個連通域id（像素的parent值）修改為從1開始嚴(yán)格單調(diào)增的序列，開啟LOCAL和LOCAL_DEBUG宏可以看到。

和通常用的模板寫法略有差別，比如返回root的遞歸終止條件，比如root初值。

不得不說，uDebug是個好東西。

#include <stdio.h> #include <stdio.h> #include <string.h> #include <stdlib.h>typedef struct FSU_Node {int p; /* parent id */int rank; } FSU_Node;/* get node's root id @param x: node id @param nodes: all nodes in map */int fus_find(int x, FSU_Node* nodes) {if (nodes[x].p == x) {return x;}nodes[x].p = fus_find(nodes[x].p, nodes);return nodes[x].p; }/* merge two node groups @param a: a node from one node group @param b: a node from another node group */ void fus_union(int a, int b, FSU_Node* nodes) {int ra = fus_find(a, nodes); /* ra: root id of a */int rb = fus_find(b, nodes); /* rb: root id of b */if (ra == rb) {return;}if (nodes[ra].rank > nodes[rb].rank) {nodes[rb].p = ra;}else {if (nodes[ra].rank == nodes[rb].rank) {nodes[rb].rank++;}nodes[ra].p = rb;} }/* #define LOCAL */ /* #define LOCAL_DEBUG */ int main() { #ifdef LOCALconst char* input_txt = "F:/zhangzhuo/debug/OJ/UVA-572.txt";freopen(input_txt, "r", stdin); #endif#define MAXN 105int m, n, cnt, i, j, k;int shift_x[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };int shift_y[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };unsigned char mp[MAXN*MAXN];FSU_Node nodes[MAXN*MAXN];int idx;while (scanf("%d%d", &m, &n) == 2 && m && n) {cnt = 0;for (i = 0; i < m; i++) {for (j = 0; j < n; j++) {idx = i * n + j;scanf(" %c", &mp[idx]);}}for (i = 0; i < m; i++) {for (j = 0; j < n; j++) {idx = i * n + j;nodes[idx].p = idx;nodes[idx].rank = 1;}}for (i = 0; i < m; i++) {for (j = 0; j < n; j++) {idx = i * n + j;if (mp[idx] != '@') continue;for (k = 0; k < 8; k++) {int row = i + shift_x[k];int col = j + shift_y[k];int neighbor_idx = row * n + col;if (row < 0 || row >= m || col < 0 || col >= n || mp[neighbor_idx] != '@') continue;fus_union(idx, neighbor_idx, nodes);}}}int bowl[MAXN*MAXN] = { 0 };int label_cnt = 0;for (i = 0; i < m*n; i++) {if (mp[i] != '@') continue;int t = fus_find(i, nodes);nodes[i].p = t;if (bowl[t] == 0) {label_cnt++;bowl[t] = label_cnt;} }printf("%d\n", label_cnt);#ifdef LOCAL_DEBUG/* print out debug info */for (i = 0; i < m; i++) {for (j = 0; j < n; j++) {idx = i * n + j ;if (mp[idx] == '@') {/* printf("%3d", fus_find(idx, nodes)); *//* printf("%3d", nodes[idx].p); */printf("%3d", bowl[nodes[idx].p]);}else {printf("%3c", '*');}}printf("\n");}printf("\n"); #endif}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/zjutzz/p/11017619.html

總結(jié)

以上是生活随笔為你收集整理的UVA572 Oil Deposits DFS求解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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