ZOJ 1047 Image Perimeters（BFS搜索）
题目比较长，题目中给你解释了一个样例。
我大概说一下题目的意思，题目给你一个地图，包含字符X和.。
给你一个起点，让你从8个方向去搜索，找X连通块的周长。
如果还没太理解，可以看下题目中图二的例子，题目给定的起点就是2,3；
从这个起点出发，往8个方向扩展以后得到的连通块就是图中圈出来的部分。
这一部分的周长数一数，可以数出来是18。
这一道题目的数据范围比较小，行和列只有20.可以用搜索做。
这里我用的是广度优先搜索BFS。
处理周长的方法：当以一个点为出发点出发时，搜索8个方向，如果这8个方向中的
上 左 下 右这四个方向有一个方向没有X，周长就加1
我大概说一下题目的意思，题目给你一个地图，包含字符X和.。
给你一个起点，让你从8个方向去搜索，找X连通块的周长。
如果还没太理解，可以看下题目中图二的例子，题目给定的起点就是2,3；
从这个起点出发，往8个方向扩展以后得到的连通块就是图中圈出来的部分。
这一部分的周长数一数，可以数出来是18。
这一道题目的数据范围比较小，行和列只有20.可以用搜索做。
这里我用的是广度优先搜索BFS。
处理周长的方法：当以一个点为出发点出发时，搜索8个方向，如果这8个方向中的
上 左 下 右这四个方向有一个方向没有X，周长就加1
这样处理下来得到的就是答案
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<functional> #include<queue> using namespace std; int n,m,s,e,sum; char maps[200][200]; int vis[200][200]; int next[8][2]={-1,0,0,-1,1,0,0,1,-1,-1,1,-1,1,1,-1,1};//方向数组 //上 左 下 右 左上 左下 右下 右上 struct node { int x,y; }k,tmp; queue<node> que; void bfs() { int x,y,i; while(que.size()) { k=que.front(); que.pop(); for(i=0;i<8;i++) { x=k.x+next[i][0]; y=k.y+next[i][1]; if(maps[x][y]=='X'&&!vis[x][y]) { tmp.x=x; tmp.y=y; vis[x][y]=1; que.push(tmp); } else if(i<=3&&maps[x][y]!='X')//上左下右四个方向 sum++; } } } int main() { int i,j; while(scanf("%d%d%d%d",&n,&m,&s,&e)!=EOF) { sum=0; memset(maps,0,sizeof(maps)); memset(vis,0,sizeof(vis));//清空标记 getchar(); if(n==0&&m==0&&s==0&&e==0) break; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) scanf("%c",&maps[i][j]); getchar(); } tmp.x=s; tmp.y=e; vis[s][e]=1; que.push(tmp); bfs(); printf("%d\n",sum); } return 0; } 
投递快手等公司10个岗位 >
查看10道真题和解析
