posts - 33,  comments - 33,  trackbacks - 0
大意:给出一个区域图和Click的坐标,求击中区域的周长
题解:爆搜,BFS出整个连通域,注意求周长是上下左右的连通域,所以将8连域分成两个4连域,然后在BFS时一并计算出周长
代码:
#include <stdio.h>
#include 
<queue>
using namespace std;

const int dsx1[4= {1,0,-1,0};
const int dsy1[4= {0,1,0,-1};
const int dsx2[4= {1,-1,-1,1};
const int dsy2[4= {1,1,-1,-1};

int width;
int height;
int startX,startY;
char Maps[25][25];
bool visited[25][25];

const bool bound(int _x,int _y)
{
    
return (_x >=0 && _x < width)&&(_y >= 0 && _y < height);
}


int BFS()
{
    
int ret = 0;
    
if (Maps[startY][startX] !='X')
    
{
        
return 0;
    }

    memset(visited,
0,sizeof(visited));
    queue
<int> que;
    que.push(startY
*100 + startX);
    visited[startY][startX] 
= true;
    
while(!que.empty())
    
{
        
int curId = que.front();
        que.pop();
        
int curX = curId % 100;
        
int curY = curId / 100;
        
int newX,newY;
        
for (int i = 0; i < 4++i)
        
{
            newX 
= curX + dsx1[i];
            newY 
= curY + dsy1[i];
            
if (bound(newX,newY))
            
{
                
if (!visited[newY][newX])
                
{    
                    
if (Maps[newY][newX] == 'X')
                    
{
                        visited[newY][newX] 
= true;
                        que.push(newY
*100 + newX);
                    }

                    
else
                    
{
                        
//add
                        ++ret;
                    }

                }

            }

            
else
            
{
                
++ret;
            }

        }

        
for (int i = 0; i < 4++i)
        
{
            newX 
= curX + dsx2[i];
            newY 
= curY + dsy2[i];
            
if (bound(newX,newY))
            
{
                
if (!visited[newY][newX])
                
{        
                    
if (Maps[newY][newX] == 'X')
                    
{
                        
                        visited[newY][newX] 
= true;
                        que.push(newY
*100 + newX);
                    }

                }

            }

        }

    }

    
return ret;
}


void Test()
{
    memset(Maps,
0,sizeof(Maps));
    
for (int i = 0; i < height; ++i)
    
{
        scanf(
"%s",Maps[i]);
    }

    printf(
"%d\n",BFS());
}


int main()
{
    
//freopen("data.txt","r",stdin);
    while(scanf("%d %d %d %d",&height,&width,&startY,&startX) != EOF)
    
{
        
if (height == 0)
        
{
            
break;
        }

        
--startY;
        
--startX;
        Test();
    }

    
return 0;
}


posted on 2011-11-09 12:34 bennycen 阅读(1475) 评论(1)  编辑 收藏 引用 所属分类: 算法题解

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理