1226. [S/W 문제해결 기본] 7일차 - 미로1

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include<queue>
#include<utility>


using namespace std;

struct se{
    int x,y;
    se(int x, int y){
        this->x = x;
        this->y = y;
    }
};

int map[17][17];
bool d[17][17];
se start = se(0,0);
se endi = se(0,0);
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

void bfs(int x, int y){
    queue<pair<int,int>> q;
    q.push({x,y});
    d[x][y] = true;
    while(!q.empty()){
        x = q.front().first; y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x+dx[i]; int ny = y+dy[i];
            if(nx>= 1 && nx <= 16 && ny >=1  && ny <= 16){
                    if(d[nx][ny] ==false){
                        if(map[nx][ny] != 1) {
                            d[nx][ny] = true;
                            q.push({nx, ny});
                        }

                    }
            }
        }
    }

}

int main(){
    for(int t = 1 ; t<=10; t++){
        memset(d, false , sizeof(d));
        int tc;
        cin>>tc;
        for(int i = 1; i <= 16; i++){
            for(int j = 1; j <= 16; j++){
                scanf("%1d",&map[i][j]);
                if(map[i][j] == 2)
                    start = se(i,j);
                if(map[i][j] == 3)
                    endi = se(i,j);
            }
        }
        bfs(start.x, start.y);
        cout<<'#'<<tc;
        if(d[endi.x][endi.y] == true){
            cout<<" "<<1;
        } else cout<<" "<<0;
        cout<<'\n';

    }

    return 0;
}

 

굉장히 간단한 BFS 문제다. 테스트케이스마다 전체적으로 탐색한번씩하고 -> 처음시작하면서 초기화하는문제

BFS까먹을까봐풀었음