首页 > 代码库 > poj 1979 Red and Black

poj 1979 Red and Black

题目链接:http://poj.org/problem?id=1979

 

思路:

DFS搜索法解决,与迷宫问题相似;

迷宫由于搜索方向只往左或右一个方向,往上或下一个方向,不会出现重复搜索;在该问题中往四个方向搜索,会重复搜索;

所以使用vis表来标记访问过的点,避免重复搜索。

 

代码: 

#include <iostream>using namespace std;const int MAX_N = 25;int vis[MAX_N][MAX_N];char map[MAX_N][MAX_N];int red_count, W, H;int Search( int i, int j ){    if ( i == 0 || i == H + 1             || j == 0 || j == W + 1 )        return 0;    else    if ( map[i][j] == # )        return 0;    else    if ( !vis[i][j] )    {        vis[i][j] = 1;        red_count++;           Search( i-1, j );        Search( i+1, j );        Search( i, j-1 );        Search( i, j+1 );    }    return 0;}int main(){    while ( scanf( "%d %d\n", &W, &H ) != EOF )    {        int i_start, j_start;        red_count = 0;        memset( map, 0, sizeof(map) );        memset( vis, 0, sizeof(vis) );        if ( W == 0 && H == 0 )            break;        for ( int h = 1; h <= H; ++h )            for ( int w = 1; w <= W; ++w )            {                scanf( "%c", &map[h][w] );                if ( map[h][w] == @ )                {                    i_start = h;                    j_start = w;                }                scanf( "\n" );            }        Search( i_start, j_start );        cout << red_count << endl;     }        return 0;}

 

poj 1979 Red and Black