【HDOJ】1241 Oil Deposits

经典的BFS。

 #include <stdio.h>
#include <string.h> #define MAXNUM 105
#define MAXROW 105
#define MAXQUE 10005 char buf[MAXROW][MAXNUM];
char visit[MAXROW][MAXNUM]; typedef struct {
int x, y;
} pos_st; pos_st queue[MAXQUE];
int direct[][] = {{,-},{-,-},{-,},{-,},{,},{,},{,},{,-}};
int m, n;
int total; void bfs();
void search(); int main() {
int i; while (scanf("%d%d", &m, &n)!=EOF && (m||n)) {
getchar();
for (i=; i<m; ++i) {
gets(buf[i]);
}
bfs();
printf("%d\n", total);
} return ;
} void bfs() {
int i, j; total = ;
memset(visit, -, sizeof(visit)); for (i=; i<m; ++i)
for (j=; j<n; ++j)
if (buf[i][j]=='@' && visit[i][j]==-)
search(i, j);
} void search(int row, int col) {
int front, rear;
int x, y, newx, newy;
int i; front = rear = ;
total++;
visit[row][col] = total; if (visit[row][col] > ) {
queue[rear].x = row;
queue[rear].y = col;
rear++;
while (front != rear) {
x = queue[front].x;
y = queue[front].y;
front++;
for (i=; i<; ++i) {
newx = x+direct[i][];
newy = y+direct[i][];
if (newx>= && newx<m && newy>= && newy<n) {
if (buf[newx][newy] == '@' && visit[newx][newy]<) {
queue[rear].x = newx;
queue[rear].y = newy;
rear++;
visit[newx][newy] = total;
}
}
}
}
} }
上一篇:从SQL2008R2导入数据到SQL2005


下一篇:【Android Developers Training】 94. 创建一个空内容提供器(Content Provider)