您现在的位置是:首页 > 学习之路 > ACM||算法ACM||算法

POJ-3984 迷宫问题

卞振伟2019-07-25【ACM||算法】人已围观

简介POJ-3984 迷宫问题
BFS
迷宫含有墙跟路,输出左上角到右下角最短的路径
BFS路径用string

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;

const int maxn = 110;

int n, m;
char mp[maxn][maxn];
bool vst[maxn][maxn];
int ans = 0;
int step[9][2] = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};

bool check(int x, int y){
    if(x < 0 || x >= n || y < 0 || y >= m)
        return false;
    if(vst[x][y])
        return false;
    return true;
}

void dfs(int x, int y){
    for(int i = 0; i < 9; ++i){
        int cur_x = x + step[i][0];
        int cur_y = y + step[i][1];
        if(check(cur_x, cur_y) && mp[cur_x][cur_y] == '@'){
            vst[cur_x][cur_y] = 1;
            dfs(cur_x, cur_y);
        }
    }
}

int main(){
    while(~scanf("%d%d", &n, &m)){
        if(!n || !m)
            return 0;
        ans = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++){
                cin >> mp[i][j];
                vst[i][j] = 0;
            }
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j){
                if(mp[i][j] == '@' && !vst[i][j]){
                    dfs(i, j);
                    ans++;
                }
            }
        cout << ans << endl;
    }
    return 0;
}

Tags:ACM   编程   个人   题解   算法   C|C++

很赞哦! ()

上一篇:UVA-11624 Fire

下一篇:HDU-1241 Oil Deposits

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:118篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00