UVa 572 - Oil Deposits 搜索专题-白红宇

UVa 572 - Oil Deposits 搜索专题

阅读量：4074 次

发布时间：2019-05-25

本文共 1873 字，大约阅读时间需要 6 分钟。

11158

58.77%

5511

95.30%

题目链接：

题目类型：搜索

样例输入：

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

样例输出：

分析：

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

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

代码1： DFS

#include
   
    #include
    
     #include
     
      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
      
       =0 && dy

代码2：

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

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

#include
   
    #include
    
     #include
     
      #include
      
       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
       
        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
        
         =0 && dy

代码3： BFS

#include
   
    #include
    
     #include
     
      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
      
       =0 && dy