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

POJ-1321 棋盘问题

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

简介POJ-1321 棋盘问题
DFS
八皇后问题维护一个一维数组表示该列是否访问过
坑:回溯 可能存在k

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cstdio>

using namespace std;

const int maxn = 110;
int t, n, m;
int mp[maxn][maxn][maxn];
int vst[maxn][maxn][maxn];
int sz,sx,sy,ez,ex,ey;
int step[6][3] = {{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};

struct  Point{
    int x,y,z;
    int d;
    Point(int zz, int xx, int yy, int dis){
        z = zz;
        x = xx;
        y = yy;
        d = dis;
    }
    Point(){}
};

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

int ans;

void bfs(){
    queue<Point> q;
    q.push(Point(sz,sx,sy,0));
    while(!q.empty()){
        Point p = q.front();
        q.pop();
        if(p.z == ez && p.x == ex && p.y == ey){
            ans = p.d;
            printf("Escaped in %d minute(s).\n", ans);
            return;
        }
        for(int i = 0; i < 6; ++i){
            int cur_z = p.z + step[i][0];
            int cur_x = p.x + step[i][1];
            int cur_y = p.y + step[i][2];
            if(!vst[cur_z][cur_x][cur_y] && check(cur_z, cur_x, cur_y)){
                vst[cur_z][cur_x][cur_y] = 1;
                q.push(Point(cur_z,cur_x,cur_y, p.d+1));
            }
        }
    }
    printf("Trapped!\n");
}

int main(){
    while(~scanf("%d%d%d", &t, &n, &m)){
        if(!t || !n || !m)
            return 0;
        getchar();
        memset(vst, 0, sizeof(vst));
        for(int k = 0; k < t; ++k){
            for(int i = 0; i < n; ++i){
                for(int j = 0; j < m; ++j){
                    scanf("%c", &mp[k][i][j]);
                    if(mp[k][i][j] == 'S'){
                        sz = k;
                        sx = i;
                        sy = j;
                    }
                    if(mp[k][i][j] == 'E'){
                        ez = k;
                        ex = i;
                        ey = j;
                    }
                }
                getchar();
            }
            if(k != t-1)
                getchar();
        }
        ans = 0;
        bfs();
    }
    return 0;
}

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

很赞哦! ()

文章评论

站点信息

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

客服在线

QQ客服

客服微信扫码

服务时间

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