首页 > 代码库 > 【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