문제 링크
https://www.acmicpc.net/problem/1194
문제 해결
1. 기본적인 BFS에 비트마스크를 추가한 형태로 해결. visit[row][column][key_bitmask]
주의할 점
1. 같은 시간대를 구현하기 위해서 큐의 크기를 이용.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
explanation in vjerksen.tistory.com | |
*/ | |
#include<cstdio> | |
#include<cstdlib> | |
#include<iostream> | |
#include<string> | |
#include<deque> | |
#include<vector> | |
#include<algorithm> | |
#include<queue> | |
#include<set> | |
#include<cmath> | |
using namespace std; | |
int N,M,s_row,s_col,ans; | |
int row_move[]={0,0,-1,1}; | |
int col_move[]={-1,1,0,0}; | |
char miro[55][55]; | |
bool visit[55][55][65]; // row,col,key | |
bool flag; | |
void bfs(int row, int col){ | |
queue<pair<pair<int, int>,int> > q; | |
visit[row][col][0]=true; | |
q.push({{row,col},0}); | |
while(!q.empty()){ | |
// caution 1 | |
int q_size = q.size(); | |
while(q_size--){ | |
int c_row = q.front().first.first; | |
int c_col = q.front().first.second; | |
int c_key = q.front().second; | |
if(miro[c_row][c_col] == '1'){ | |
flag = true; | |
return; | |
} | |
q.pop(); | |
for(int i=0;i<4;i++){ | |
int n_row = c_row+row_move[i]; | |
int n_col = c_col+col_move[i]; | |
int n_key = c_key; | |
if(n_row<0||n_row>=N||n_col<0||n_col>=M) | |
continue; | |
if(miro[n_row][n_col]=='#') | |
continue; | |
if(miro[n_row][n_col]>='a'&&miro[n_row][n_col]<='f'){ | |
n_key |= (1 << (miro[n_row][n_col]-'a')); | |
} | |
if(miro[n_row][n_col]>='A'&&miro[n_row][n_col]<='F'){ | |
if(!(n_key & (1 << (miro[n_row][n_col]-'A')))) | |
continue; | |
} | |
if(!visit[n_row][n_col][n_key]){ | |
visit[n_row][n_col][n_key]=true; | |
q.push({{n_row,n_col},n_key}); | |
} | |
} | |
} | |
ans++; | |
} | |
} | |
int main(){ | |
scanf("%d %d\n",&N,&M); | |
for(int i=0;i<N;i++){ | |
scanf("%s",miro[i]); | |
for(int j=0;j<M;j++){ | |
if(miro[i][j] == '0'){ | |
s_row = i; | |
s_col = j; | |
} | |
} | |
} | |
bfs(s_row,s_col); | |
if(flag) printf("%d",ans); | |
else puts("-1"); | |
return 0; | |
} |
※ 정확하고 부드러운 태클은 언제나 환영입니다.
'Problem Solving' 카테고리의 다른 글
BOJ 2002 - 추월 (0) | 2017.01.03 |
---|---|
BOJ 10546 - 배부른 마라토너 (0) | 2016.12.31 |
BOJ 1947 - 신입 사원 (0) | 2016.12.30 |
BOJ 10820 - 문자열 분석 (0) | 2016.12.18 |
BOJ 2870 - 수학숙제 (0) | 2016.12.17 |