首页 > 代码库 > poj1111 Image Perimeters 广搜
poj1111 Image Perimeters 广搜
题目大意：
输入一个矩阵，再输入其中一个“X”的位置（从1开始）。从该位置向八个方向扩展，如果是“X”就可以并在一起。问最后得到的模块的周长是多少。
解题思路：
按照广搜的思路来做。用一个二维的数组标记每一个点，-1代表着该点不能被搜索了（可能原本就是“.”，也可以该点已经出队列了）；0代表着该点还没被搜到；1代表着该点已经被搜到，但是还在队列中。
初始周长为4，代表只有一个X时的周长。对于每一个点，如果是“X”，就初始化为标记为0；如果是"."就初始化为-1。
对于当前进行搜索的X的上下左右四个方向上的X，如果被搜到过（就是说那个点在队列中），就把当前的周长减2；如果上下左右的X没有被搜到过，周长加2，并且把那个点入队，并且标记为1。原因：两个在横向和纵向上相邻的X，它们之间和在一起的周长是４＋４－２＝４＋２，相当于是一个X的周长＋２。对于被搜到过的X，由于它又与其它的X相邻，所以周长需要减２。
对于当前进行搜索的X的东南、西南、东北、西北四个方向的X，如果没有被搜到过，周长加4。
最后输出周长就可以了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 8 const int N=22; 9 int dx[8]={0,0,1,-1,1,1,-1,-1};10 int dy[8]={1,-1,0,0,1,-1,1,-1};11 12 int vis[N][N];13 int r,c,s,sx,sy;14 struct node15 {16 int x,y;17 };18 node a,b;19 bool isin(int x,int y)20 {21 return x>=0&&x<r&&y>=0&&y<c;22 }23 queue<node> q;24 void BFS()25 {26 while(!q.empty())27 {28 a=q.front(); q.pop();29 vis[a.x][a.y]=-1;30 int i;31 for(i=0;i<4;i++)32 {33 int x=a.x+dx[i],y=a.y+dy[i];34 if(isin(x,y)&&vis[x][y]==1)35 {36 s-=2;37 vis[x][y]=1;38 }39 if(isin(x,y)&&!vis[x][y])40 {41 s+=2;42 b.x=x; b.y=y;43 q.push(b);44 vis[x][y]=1;45 }46 }47 for(i=4;i<8;i++)48 {49 int x=a.x+dx[i],y=a.y+dy[i];50 if(isin(x,y)&&!vis[x][y])51 {52 s+=4;53 b.x=x; b.y=y;54 q.push(b);55 vis[x][y]=1;56 }57 }58 }59 printf("%d\n",s);60 }61 int main()62 {63 //freopen("test.txt","r",stdin);64 char ch;65 while(scanf("%d%d%d%d",&r,&c,&sx,&sy)!=EOF&&r)66 {67 for(int i=0;i<r;i++){68 getchar();69 for(int j=0;j<c;j++){70 scanf("%c",&ch);71 if(ch==‘X‘) vis[i][j]=0;72 else vis[i][j]=-1;73 }74 }75 a.x=sx-1; a.y=sy-1; s=4;76 while(!q.empty()) q.pop();77 q.push(a);78 BFS();79 }80 return 0;81 }
//还是再从搜索开始吧。
poj1111 Image Perimeters 广搜
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。