首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。