大意:给出一个区域图和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 阅读(1503)
评论(1) 编辑 收藏 引用 所属分类:
算法题解