ACM winter vacation training 4

DFS（ Depth-first search ）

Depth first search is a method that is often used in the early stage of crawler development . Its purpose is to achieve the leaf nodes of the searched structure ( That is, those that do not contain any hyperchains HTML file ) . In a HTML In file , When a hyperlink is selected , Linked HTML The file will perform a depth first search , That is, you must search a single chain completely before searching the rest of the hyperlink results . Depth first search HTML The hyperlink on the file can't go any further , Then go back to a HTML file , Continue to select the HTML Other hyperlinks in the file . When there are no more hyperchains to choose from , Indicates that the search is over .

The basic idea

The method of depth first traversal graph is , From some vertex in the picture v set out ：
（1） Visit vertex v;
（2） Successively v Of the adjacent points that are not accessed , Depth first traversal of the graph ; Until the graph neutralizes v Vertices that have paths are all accessed ;
（3） If there are still vertices in the graph that are not accessed , From a vertex that has not been visited , Do depth first traversal again , Until all the vertices in the graph have been visited .　 Of course , When people have just mastered depth first search, they often use it to go through the maze . In fact, we have other ways , That's breadth first search (BFS).

Code example

int ans,sx,sy,W,H;
int dx[4]={
    0,0,1,-1};
int dy[4]={
    1,-1,0,0};
void dfs(int x,int y){
    
	for(int i=0;i<=3;i++){
    
		int tx=x+dx[i],ty=y+dy[i];
		if(a[tx][ty]=='#'){
    
			a[tx][ty]='.';
			dfs(tx,ty);
		}
	}
}

Title Example

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles.

Write a program to count the number of black tiles which he can reach by repeating the moves described above.

input

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.

There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.

‘.’ - a black tile
‘#’ - a red tile
‘@’ - a man on a black tile(appears exactly once in a data set)

output

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

Sample Input

6 9
…#.
…#
…
…
…
…
…
#@…#
.#…#.
11 9
.#…
.#.#######.
.#.#…#.
.#.#.###.#.
.#.#…@#.#.
.#.#####.#.
.#…#.
.#########.
…
11 6
…#…#…#…
…#…#…#…
…#…#…###
…#…#…#@.
…#…#…#…
…#…#…#…
7 7
…#.#…
…#.#…
###.###
…@…
###.###
…#.#…
…#.#…
0 0

Sample Output

45
59
6
13

Code example

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;

int w,h,sx,sy,ans;
char map[21][21];// Element container 
int dx[4]={
    0,0,1,-1};// Move up, down, left and right 
int dy[4]={
    1,-1,0,0};
bool v[21][21];// Check whether the cell has been detected 
void dfs(int x,int y)//DFS Depth first search algorithm 
{
    
    
    for(int i=0;i<=3;i++)
    {
    
        int tx=x+dx[i],ty=y+dy[i];// Up, down, left and right coordinate positions 
        if(tx>=1&&tx<=h&&ty>=1&&ty<=w&&map[tx][ty]!='#'&&v[tx][ty]==0)// Determine whether it is the target element 
        {
    
            ans++;// Increase in the number of results 
            v[tx][ty]=1;// Tag target cell has been detected 
            dfs(tx,ty);// Iterate through the remaining positions dfs
        }
    }
}
int main()// The main function 
{
    
    while(cin>>w>>h&&w!=0&&h!=0)// Input w,h value 
    {
    
        ans=0;// initialization 
        for(int i=1;i<=h;i++)
               for(int j=1;j<=w;j++)
              {
    
                  cin>>map[i][j];
                  if(map[i][j]=='@')// Find the person's location 
                  {
    
                      sx=i;
                      sy=j;
                  }
              }
        memset(v,0,sizeof(v));// initialization 
        v[sx][sy]=1;// Tag target cell has been detected 
        dfs(sx,sy);// quote dfs lookup 
        cout<<ans+1<<endl;// Output 
    }
    return 0;
}