POJ 1111 Image Perimeters(简单DFS)
http://poj.org/problem?id=1111
题意:(L又是一道题意复杂的简单题)给你一个R*C的仅有字符’.’(表空格)和字符’X’(表物体)构成的棋盘,现在在给你一个坐标(从1计数),要你算出这个与这个坐标点相连的所有’X’构成物体的外表面周长.
如上的棋盘,构成了两个X物体,其中下面那个小的外周长为4,右上那个大的外周长为18.
分析:
直接从给定的格子进行8个方向探索即可,每走到一个格子,首先判断该X格子是不是边界格子,如果是则返回加上周长,并且标记该格子已经走过了即可.
AC代码:注意memset(map,'.',sizeof(map));
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=30;
int R,C,sr,sc;
char map[maxn][maxn];
int dr[]={-1,1,0,0,-1,1,-1,1};//上下左右,左上,左下,右上,右下
int dc[]={0,0,-1,1,-1,-1,1,1};
int DFS(int r,int c)//返回由(r,c)格组成物品的外周长
{
if(map[r][c]=='.'||map[r][c]=='Y') return 0; //'Y'表示已探索
map[r][c]='Y';
int sum=0;
for(int d=0;d<4;d++)
sum+= map[r+dr[d]][c+dc[d]]=='.'?1:0;
for(int d=0;d<8;d++)
sum+= DFS(r+dr[d],c+dc[d]);
return sum; //错误,忘写返回值了
}
int main()
{
while(scanf("%d%d%d%d",&R,&C,&sr,&sc)==4&&R)
{
memset(map,'.',sizeof(map)); //注意,memset的这种写法
for(int i=1;i<=R;i++)
for(int j=1;j<=C;j++)
scanf(" %c",&map[i][j]);
printf("%d\n",DFS(sr,sc));
}
return 0;
}
分享到:
相关推荐
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
北大POJ1020-Anniversary Cake 解题报告+AC代码
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
poj openjudge 1111题最大正向匹配 提交ac
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ初级-简单搜索 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj2599,简单dfs可以过此题,按顺序搜到任意可行解即可。
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告