UVa 572：Oil Deposits 搜索专题

UVa 572：Oil Deposits 搜索专题2014-10-06 shuangde800 题目链接：

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=513

题目类型：搜索

样例输入：

1 1*3 5*@*@***@***@*@*1 8@@****@*5 5****@*@@*@*@**@@@@*@@@**@0 0

样例输出：

分析：

这一题可以说是搜索中最基础的一题之一。要找出相连在一起的有多少块，因此，依次枚举，遇到@时就进行搜索，用深搜，广搜都行，目的是把相连的@都标记为已访问。

下面给出用DFS（深搜）和BFS（广搜）的代码。

代码1： DFS

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int m,n;int dir[8][2] = {{-1,0},{-1,1},{0,1},{1,1}, { 1,0},{1,-1},{0,-1},{-1,-1}};bool vis[105][105];char map[105][105]; void dfs（int x, int y）{for（int i=0; i<8; ++i）{int dx=x+dir[i][0], dy=y+dir[i][1];if（dx>=0 && dx<m && dy>=0 && dy<n && map[dx][dy]=="@" && ！vis[dx][dy]）{vis[dx][dy] = true;dfs（dx, dy）;}}} int main（）{#ifdef LOCALfreopen（"input.txt","r",stdin）;#endifint i,j;while（scanf（"%d %d%*c",&m,&n） && m && n）{for（i=0; i<m; ++i）gets（map[i]）;memset（vis, 0, sizeof（vis））;int cnt=0;for（i=0; i<m; ++i）{for（j=0; j<n; ++j）{if（map[i][j]=="@" && ！vis[i][j]）{++cnt;dfs（i, j）;}}}printf（"%d
",cnt）;}return 0;}

本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45526.htm

代码2：

以上是用递归的方式进行DFS，但是如果数据量很大，递归方式有可能栈溢出的危险！

下面是模拟栈的方式，而不是递归的方式写DFS

#include<iostream>#include<cstdio>#include<cstring>#include<stack>using namespace std;int m,n;int dir[8][2] = {{-1,0},{-1,1},{0,1},{1,1}, { 1,0},{1,-1},{0,-1},{-1,-1}};bool vis[105][105];char map[105][105];struct Node{ int x,y; };stack<Node>st; void dfs（int x, int y）{while（！st.empty（）） st.pop（）;Node temp;temp.x = x, temp.y = y;st.push（temp）;while（！st.empty（））{temp = st.top（）;st.pop（）;for（int i=0; i<8; ++i）{int dx=temp.x+dir[i][0], dy=temp.y+dir[i][1];if（dx>=0 && dx<m && dy>=0 && dy<n && map[dx][dy]=="@" && ！vis[dx][dy]）{vis[dx][dy] = true;Node t;t.x = dx, t.y = dy;st.push（t）;}}}} int main（）{#ifdef LOCALfreopen（"input.txt","r",stdin）;#endifint i,j;while（scanf（"%d %d%*c",&m,&n） && m && n）{for（i=0; i<m; ++i）gets（map[i]）;memset（vis, 0, sizeof（vis））;int cnt=0;for（i=0; i<m; ++i）{for（j=0; j<n; ++j）{if（map[i][j]=="@" && ！vis[i][j]）{++cnt;dfs（i, j）;}}}printf（"%d
",cnt）;}return 0;}

代码3： BFS

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int m,n;int dir[8][2] = {{-1,0},{-1,1},{0,1},{1,1}, { 1,0},{1,-1},{0,-1},{-1,-1}};bool vis[105][105];char map[105][105];struct Node{ int x,y; };Node que[10000]; void bfs（int x,int y）{int front=0, rear=1;que[0].x = x;que[0].y = y;while（front < rear）{Node t=que[front++];for（int i=0; i<8; ++i）{int dx=t.x+dir[i][0], dy=t.y+dir[i][1];if（dx>=0 && dx<m && dy>=0 && dy<n && map[dx][dy]=="@" && ！vis[dx][dy]）{vis[dx][dy] = true;Node temp;temp.x = dx, temp.y = dy;que[rear++] = temp;}}}} int main（）{#ifdef LOCALfreopen（"input.txt","r",stdin）;#endifint i,j;while（scanf（"%d %d%*c",&m,&n） && m && n）{for（i=0; i<m; ++i）gets（map[i]）;memset（vis, 0, sizeof（vis））;int cnt=0;for（i=0; i<m; ++i）{for（j=0; j<n; ++j）{if（map[i][j]=="@" && ！vis[i][j]）{++cnt;bfs（i, j）;}}}printf（"%d
",cnt）;}return 0;}