UVa 784 - Maze Exploration 搜索专题

784-Maze Exploration

7758

41.30%

2328

84.06%

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=725

样例输入：

2
XXXXXXXXX
X   X   X
X *     X
X   X   X
XXXXXXXXX
X   X
X   X
X   X
XXXXX
_____
XXXXX
X   X
X * X
X   X
XXXXX
_____

样例输出：

XXXXXXXXX
X###X###X
X#######X
X###X###X
XXXXXXXXX
X   X
X   X
X   X
XXXXX
_____
XXXXX
X###X
X###X
X###X
XXXXX
_____

分析：

又是一道搜索入门的简单题，不解释。 天天刷水题，今天特别多。今天的度假很happy，在这样的大热天，就应该水水降降温。

代码1： DFS

#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;

char map[35][100];
int vis[35][100], row;
int dir[4][2] = {{-1,0}, {0,1}, {1,0}, {0,-1}};

inline bool isWall(char ch){
    if(isprint(ch) && ch!=' ' && ch!='*' && ch!='-') return true;
    return false;
}

void dfs(int x,int y){
    for(int i=0; i<4; ++i){
        int dx=x+dir[i][0], dy=y+dir[i][1];
        if(dx>=0 && dx<row && dy>=0 && dy<strlen(map[dx]) && !isWall(map[dx][dy]) && map[dx][dy]!='#' && !vis[dx][dy]){
            vis[dx][dy] = true;
            map[dx][dy] = '#';
            dfs(dx, dy);
        }
    }
}

int main(){
#ifdef LOCAL
    freopen("input.txt","r",stdin);
#endif  
    int T, start_x, start_y;
    scanf("%d%*c", &T);
    while(T--){
        row=0;
        bool isFind = false;
        while(gets(map[row])){
            if(map[row][0]=='_') break;
            if(!isFind){
                for(int i=0; i<strlen(map[row]); ++i){
                    if(map[row][i]=='*'){
                        start_x = row, start_y = i;
                        isFind = true;
                        break;
                    }
                }
            }
            ++row;
        }
        memset(vis, 0, sizeof(vis));
        dfs(start_x, start_y);
        for(int i=0; i<=row; ++i)
            puts(map[i]);
    }
    return 0;
}

代码2：BFS

#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;

char map[35][100];
int vis[35][100], row;
int dir[4][2] = {{-1,0}, {0,1}, {1,0}, {0,-1}};
struct Node{int x,y; };
Node que[10000];

inline bool isWall(char ch){
    if(isprint(ch) && ch!=' ' && ch!='*' && ch!='-') return true;
    return false;
}

void bfs(int x,int y){
    int front=0, rear=1;
    que[0].x = x, que[0].y = y;

    while(front<rear){
        Node t = que[front++];
        for(int i=0; i<4; ++i){
            int dx=t.x+dir[i][0], dy=t.y+dir[i][1];
            if(dx>=0 && dx<row && dy>=0 && dy<strlen(map[dx]) && !isWall(map[dx][dy]) && map[dx][dy]!='#' && !vis[dx][dy]){
                vis[dx][dy] = true;
                map[dx][dy] = '#';
                Node q;
                q.x = dx, q.y = dy;
                que[rear++] = q;
            }
        }
    }
}

int main(){
#ifdef LOCAL
    freopen("input.txt","r",stdin);
#endif  
    int T, start_x, start_y;
    scanf("%d%*c", &T);
    while(T--){
        row=0;
        bool isFind = false;
        while(gets(map[row])){
            if(map[row][0]=='_') break;
            if(!isFind){
                for(int i=0; i<strlen(map[row]); ++i){
                    if(map[row][i]=='*'){
                        start_x = row, start_y = i;
                        isFind = true;
                        break;
                    }
                }
            }
            ++row;
        }
        memset(vis, 0, sizeof(vis));
        bfs(start_x, start_y);
        for(int i=0; i<=row; ++i)
            puts(map[i]);
    }
    return 0;
}