HDU1312 Red and Black(搜索)

题目链接。

分析:

水题，直接BFS或者DFS。

dfs:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 22

char G[MAXN][MAXN];
int vis[MAXN][MAXN], cnt, m, n;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void dfs(int x, int y){
    int d;
    for(d=0; d<4; d++){
        int nx = x+dx[d], ny = y+dy[d];
        if(nx >= 0 && nx < n && ny >= 0 && ny < m && G[nx][ny] == '.' && !vis[nx][ny]){
            cnt++;
            vis[nx][ny] = 1;
            dfs(nx, ny);
        }
    }
}

int main(){
    int i, j;
    while(scanf("%d %d", &m, &n) == 2 && (m != 0 || n != 0)){
        cnt = 1;
        memset(vis, 0, sizeof(vis));

        for(i=0; i<n; i++){
            scanf("%s", G[i]);
        }

        for(i=0; i<n; i++){
            for(j=0; j<m; j++){
                if(G[i][j] == '@') break;
            }
            if(j<m) break;
        }
        vis[i][j] = 1;
        dfs(i,j);
        printf("%d\n", cnt);
    }

    return 0;
}

bfs:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 22

typedef struct Pos{
    int x, y;
}Pos;

Pos queue[MAXN*MAXN];
char G[MAXN][MAXN];
int vis[MAXN][MAXN], cnt, m, n;

int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

void bfs(int x, int y){
    Pos pos;
    int front, rear, d;
    memset(vis, 0, sizeof(vis));
    front = rear = 0;
    pos.x = x; pos.y = y;;
    queue[rear++] = pos;
    vis[x][y] = 1;
    while(front < rear){
        pos = queue[front++];
        cnt++;
        for(d=0; d<4; d++){
            int nx = pos.x+dx[d], ny = pos.y+dy[d];
            if(nx>=0 && nx<n && ny>=0 && ny<m && !vis[nx][ny] && G[nx][ny] == '.'){
                vis[nx][ny] = 1;
                queue[rear].x = nx;
                queue[rear++].y = ny;
            }
        }
    }
}

int main(){
    int i, j;
    while(scanf("%d %d", &m, &n) == 2 && (m != 0 || n != 0)){
        cnt = 0;
        for(i=0; i<n; i++){
            scanf("%s", G[i]);
        }

        for(i=0; i<n; i++){
            for(j=0; j<m; j++){
                if(G[i][j] == '@') break;
            }
            if(j<m) break;
        }

        bfs(i,j);
        printf("%d\n", cnt);
    }

    return 0;
}