首页 > 代码库 > 【HDOJ】3316 Mine sweeping
【HDOJ】3316 Mine sweeping
简单BFS。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <queue> 6 using namespace std; 7 8 #define MAXN 105 9 10 typedef struct node_t {11 int x, y;12 node_t() {}13 node_t(int xx, int yy) {14 x = xx; y = yy;15 }16 } node_t;17 18 char map[MAXN][MAXN];19 char ans[MAXN][MAXN];20 bool visit[MAXN][MAXN];21 int dir[8][2] = {22 {-1,0},{1,0},{0,1},{0,-1},23 {1,1},{1,-1},{-1,1},{-1,-1}24 };25 node_t s;26 int n;27 28 bool check(int x, int y) {29 return x<0 || x>=n || y<0 || y>=n;30 }31 32 void bfs() {33 int i, j, k, tmp;34 int x, y, v;35 int xx[8], yy[8], m;36 queue<node_t> Q;37 node_t nd;38 39 memset(visit, false, sizeof(visit));40 memset(ans, ‘.‘, sizeof(ans));41 visit[s.x][s.y] = true;42 for (i=0; i<n; ++i)43 ans[i][n] = ‘\0‘;44 Q.push(s);45 46 while (!Q.empty()) {47 nd = Q.front();48 Q.pop();49 v = m = 0;50 for (i=0; i<8; ++i) {51 x = nd.x + dir[i][0];52 y = nd.y + dir[i][1];53 if (check(x, y))54 continue;55 xx[m] = x;56 yy[m] = y;57 ++m;58 if (map[x][y] == ‘X‘)59 ++v;60 }61 ans[nd.x][nd.y] = v+‘0‘;62 if (v == 0) {63 for (i=0; i<m; ++i) {64 if (!visit[xx[i]][yy[i]]) {65 visit[xx[i]][yy[i]] = true;66 Q.push(node_t(xx[i], yy[i]));67 }68 }69 }70 }71 }72 73 int main() {74 int i, j;75 76 #ifndef ONLINE_JUDGE77 freopen("data.in", "r", stdin);78 #endif 79 80 while (scanf("%d", &n) != EOF) {81 for (i=0; i<n; ++i)82 scanf("%s", map[i]);83 scanf("%d %d", &s.x, &s.y);84 85 if (map[s.x][s.y] == ‘X‘) {86 printf("it is a beiju!\n\n");87 } else {88 bfs();89 for (i=0; i<n; ++i)90 printf("%s\n", ans[i]);91 printf("\n");92 }93 }94 95 return 0;96 }
【HDOJ】3316 Mine sweeping
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。