【HDOJ】2267 How Many People Can Survive

BFS。

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std; #define MAXN 305 typedef struct node_st {
int x, y;
node_st() {}
node_st(int xx, int yy) {
x = xx; y = yy;
}
} node_st; char map[MAXN][MAXN];
bool visit[MAXN][MAXN];
int direct[][] = {-,,,,,-,,};
int n, m, f, s; bool getNext(int *x, int *y) {
for (int i=; i<n; ++i) {
for (int j=; j<m; ++j) {
if (map[i][j]!='#' && visit[i][j]==false) {
*x = i;
*y = j;
return true;
}
}
}
return false;
} void bfs() {
queue<node_st> que;
node_st node;
int ff, ss, x, y;
bool flg;
int i; f = s = ;
memset(visit, false, sizeof(visit));
while () {
if (!getNext(&x, &y))
break;
ff = ss = ;
if (map[x][y] == 'o') ++ff;
if (map[x][y] == 'v') ++ss;
que.push(node_st(x, y));
visit[x][y] = true;
flg = false; while (!que.empty()) {
node = que.front();
que.pop();
for (i=; i<; ++i) {
x = node.x + direct[i][];
y = node.y + direct[i][];
if (x< || x>=n || y< || y>=m) {
flg = true;
continue;
}
if (map[x][y]!='#' && !visit[x][y]) {
que.push(node_st(x, y));
visit[x][y] = true;
if (map[x][y] == 'o') ++ff;
if (map[x][y] == 'v') ++ss;
}
}
}
if (!flg) {
if (ff > ss) f += ff;
if (ff < ss) s += ss;
}
}
printf("%d %d\n", f, s);
} int main() {
int i; while (scanf("%d %d", &n, &m) != EOF) {
for (i=; i<n; ++i)
scanf("%s", map[i]);
bfs();
} return ;
}
上一篇:qt sleep


下一篇:ThreadLocal内存泄漏真因探究(转)