POJ - 1111 Image Perimeters

題意：求'X'圍成的周長

思路：按理說每增加一個就是周長加4，但是要減去重復的地方，這裡我是用BFS做的，如果是BFS的模板思路的話是不行的，應該要先取出再標記

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 30;

struct node {
	int x,y;
};
queue qu;
int dx[] = {0,0,1,-1,1,1,-1,-1};
int dy[] = {1,-1,0,0,1,-1,1,-1};
int vis[MAXN][MAXN],R,C,sx,sy,ans;
char map[MAXN][MAXN];

int check(int x, int y) {
	if (x >= 0 && x < R && y >= 0 && y < C && map[x][y] == 'X')
		return 1;
	return 0;
}

int bfs(int r, int c) {
	node st;
	st.x = r,st.y = c;
	qu.push(st);
	while (!qu.empty()) {
		node cur = qu.front();
		qu.pop();
		if (!vis[cur.x][cur.y]) {
			ans += 4;
			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				if (check(nx, ny) && vis[nx][ny])
					ans -= 2;
			}
			vis[cur.x][cur.y] = 1;
			for (int i = 0; i < 8; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				if (check(nx, ny)) {
					st.x = nx;
					st.y = ny;
					qu.push(st);
				}
			}
		}
	}
	return ans;
}

int main() {
	while (scanf("%d%d%d%d%*c", &R, &C, &sx, &sy) != EOF && R+C+sx+sy != 0) {
		memset(map, 0, sizeof(map));
		memset(vis, 0, sizeof(vis));
		while (!qu.empty()) 
			qu.pop();
		ans = 0;
		for (int i = 0; i < R; i++)
			gets(map[i]);
		printf("%d\n", bfs(sx-1, sy-1));
	}
	return 0;
}