大意：給出一個區域圖和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 閱讀(1515)
評論(1) 編輯 收藏 引用 所屬分類:
算法題解