首页 > 代码库 > POJ 1979 Red and Black【深度优先搜索】
POJ 1979 Red and Black【深度优先搜索】
题目链接:http://poj.org/problem?id=1979
题目大意:一个矩形的房间地板被分为w*h个小块,每一个小块不是红的就是黑的,你首先站在一个黑色小块上,你只能朝你的四个方向(上下左右)移动,且不能到达红色的小块上,问你最多能到达多少个小块。
很简单的dfs深度优先搜索
没搜索过一个格子,将该格子设置为红色,之后的搜索就不会再搜索到该格子,就不会造成重复,因为该题有很多数据,记得每次处理数据是初始化各数组及其他数据。
代码如下:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define N 22 using namespace std; int w,h; char tile[N][N]; int ans; void bfs(int row,int column) { if(row<0||column<0||row>h||column>w) return ; else { ans++; if(tile[row+1][column]=='.') { tile[row+1][column]='#'; bfs(row+1,column); } if(tile[row-1][column]=='.') { tile[row-1][column]='#'; bfs(row-1,column); } if(tile[row][column+1]=='.') { tile[row][column+1]='#'; bfs(row,column+1); } if(tile[row][column-1]=='.') { tile[row][column-1]='#'; bfs(row,column-1); } } } int main() { scanf("%d%d",&w,&h); int row,column; while(w!=0&&h!=0) { ans=0; for(int i=0;i<h;i++) scanf("%s",tile[i]); for(int i=0;i<h;i++) for(int j=0;j<w;j++) { if(tile[i][j]=='@') { row=i; column=j; tile[i][j]='#'; } } bfs(row,column); printf("%d\n",ans); memset(tile,0,sizeof(tile)); scanf("%d%d",&w,&h); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。