首页 > 代码库 > POJ - 1111 Image Perimeters
POJ - 1111 Image Perimeters
题意:求‘X‘围成的周长
思路:按理说每增加一个就是周长加4,但是要减去重复的地方,这里我是用BFS做的,如果是BFS的模板思路的话是不行的,应该要先取出再标记
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int MAXN = 30; struct node { int x,y; }; queue<node> 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。