[16954] 움직이는 미로 탈출

문제요약

1. 8*8 배열, 1초마다 벽이 아래로 내려감.
2. 벽으로 이동할 수 없고, 벽이 내려갈 때 자신의 위치가 벽이되면 갈 수 없음.
3. 도착할 수 있으면 1, 도착할 수 없으면 0 출력.

문제풀이

1. t초후 배열 만들기 (0초, ~ 8초까지, 8*8 배열이므로)
2. 몇 초후에 내려가는 것이 중요하므로, 이를 check 배열에 설정해주어야함.
3. bfs 돌리기.

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include<cmath>
#include <sstream>
#include<string>
#include <cstring>
using namespace std;
#define MAX 1003
char d[9][8][8];
int dist[9][9];
int check[9][9][9];
int dx[9] ={-1,1,0,0,1,-1,1,-1,0};
int dy[9] = {0,0,-1,1,1,1,-1,-1,0};

typedef struct _cor {
    int x;
    int y;
    int t;
}Cor;
void makemaze (int t, int next) {
    for (int i = 0 ; i< 8 ; i++) {
        for (int j = 0 ; j< 8 ; j++) {
            d[next][i][j] = '.';
        }
    }

    for (int i = 7 ; i>= 0 ;i--) {
            for (int j = 0 ; j< 8; j++) {
                if (d[t][i][j] =='#') {
                    if(i+1<8) {
                        d[next][i+1][j] = '#';
                    }
                }
            }
    }
}

int ans =0;
void  bfs (int startx, int starty ) {
    memset(check, 0, sizeof(check));

    check[startx][starty][0] = 1;
    queue<Cor> q;

    memset(dist, -1, sizeof(dist));


    q.push(Cor{startx, starty,0});

    dist[startx][starty] =0;

    while(!q.empty()) {
        int tmpx = q.front().x;
        int tmpy = q.front().y;
        int tmpt = q.front().t;
        
        q.pop();

        if( tmpx == 0 && tmpy ==7 ) {ans =1; return ;} 
        for (int i = 0 ; i< 9 ;i++) {
        
            int t= min(tmpt+1, 8);
            int tempx = tmpx+ dx[i];
            int tempy = tmpy + dy[i];
            if (0<= tempx && tempx <8  && tempy < 8 &&  0<= tempy) {
                if ( d[t][tempx][tempy] !='#' && check[tempx][tempy][t]==0 && d[tmpt][tempx][tempy] =='.') {
                    check[tempx][tempy ][t]= 1;
                  
                    q.push(Cor{tempx, tempy, t});
                }
            }
         
        }
     
    }
    
}

int main(void) {

    cin.tie(NULL);
    ios_base::sync_with_stdio(0);
    cout.tie(NULL);
    for (int i = 0 ;i< 8 ; i++) {
        for (int j = 0 ; j < 8 ; j++) {
            cin>>d[0][i][j];
           // if (d[i][j] =='#') {
            //    wall.push_back(Cor{i,j});
           // }
        }
    }

    for (int i = 0 ; i< 8 ; i++){
        makemaze(i, i+1);
    }
    for (int k= 0 ;  k < 8 ; k ++){
      for (int i = 0 ;i< 8 ; i++) {
        for (int j = 0 ; j < 8 ; j++) {
           // cout<<d[k][i][j];
           // if (d[i][j] =='#') {
            //    wall.push_back(Cor{i,j});
           // }
        }//cout<<'\n';
    }//cout<<'\n';
    }

    bfs(7,0);
    cout<<ans;

    /*for (int i = 0 ;i< 8 ; i++) {
        for (int j = 0 ; j < 8 ; j++) {
          cout<<dist[i][j];
           // if (d[i][j] =='#') {
            //    wall.push_back(Cor{i,j});
           // }
        }
        cout<<'\n';
    }*/
    return 0;
    }