首页 > 代码库 > POJ 1111 Image Perimeters
POJ 1111 Image Perimeters
http://poj.org/problem?id=1111
题意:
给定H行W列由‘.‘和‘X‘组成的地图和起点坐标,求与起点八连通的‘X‘符号组成的图形的总边长
解法:
dfs
每到一点计算上下左右‘X‘的个数得出该点边长,并标记到过的点
代码: 724K 0MS
#include <iostream>#include <cstring>using namespace std;#define _ ios_base::sync_with_stdio(0);cin.tie(0)#define N 21#define judge(x,y) (x>=0&&x<h&&y>=0&&y<w)char map[N][N];bool vis[N][N];int h, w, sx, sy, ans, mov[8][2] = { { -1, 0}, {0, 1}, {1, 0}, {0, -1}, { -1, -1}, { -1, 1}, {1, 1}, {1, -1}};void dfs(int x, int y) { int xx, yy, cnt = 4; vis[x][y] = 1; for (int i = 0; i < 4; i++) { xx = x + mov[i][0]; yy = y + mov[i][1]; if (judge(xx, yy) && map[xx][yy] == ‘X‘) cnt--; } ans += cnt; for (int i = 0; i < 8; i++) { xx = x + mov[i][0]; yy = y + mov[i][1]; if (judge(xx, yy) && !vis[xx][yy] && map[xx][yy] == ‘X‘) dfs(xx, yy); }}int main() { _; while (cin >> h >> w >> sx >> sy && (h || w || sx || sy)) { for (int i = 0; i < h; i++) { cin >> map[i]; } ans = 0; memset(vis, 0, sizeof(vis)); dfs(sx - 1, sy - 1); cout << ans << endl; } return 0;}
POJ 1111 Image Perimeters
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。