탈주범 검거
링크
풀이
1시간도 안걸렸다 신난다아
pipe[1]~pipe[7]까지 연결된 구멍을 1 , 아니면 0 으로 해서 값 넣고, Pipe[0]을 길이라고 생각하고 0,0,0,0을 넣어줬다.(갈 수없도록)
이동 하지 못하는 경우
- 다음 갈 곳에 현재 파이프가 연결하지 못하는 경우
- 범위를 넘어가는 경우
- 이미 방문했을 경우
- 파이프를 연결하지 못하는 경우
4번 경우를 확인하기 위해 방향에 따라 다음 파이프랑 연결 할 수 있는지 확인해야 함
만약 내가 1방향 (->)으로 갈건데 다음 파이프가 {1,0,1,0}이면 가선 안된다.(3방향(<-)이 0이니까)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <queue>
#include <utility>
using namespace std;
#define p pair<int,int>
int arr[51][51],visit[51][51];
int X,Y,ans;
int dx[]={0,1,0,-1},dy[]={-1,0,1,0};
int pipe[8][4]={
{0,0,0,0},{1,1,1,1},
{1,0,1,0},{0,1,0,1},
{1,1,0,0},{0,1,1,0},
{0,0,1,1},{1,0,0,1}};
void bfs(int sy,int sx,int time){
queue<p> q;
q.push(p(sy,sx));
visit[sy][sx]=1;
ans=0;
for(int idx=0;idx<time;idx++){
int len=(int)q.size();
for(int j=0;j<len;j++){
int y=q.front().first, x=q.front().second,val=arr[y][x];
q.pop();
++ans;
for(int i=0;i<4;i++){
if(pipe[val][i]==0) continue;
int nx=x+dx[i],ny=y+dy[i], nval=arr[ny][nx];
if(nx<0 || ny <0 || nx>= X || ny >= Y) continue;
int ni= i>=2 ? i-2 : i+2 ;
if(visit[ny][nx]==1 || pipe[nval][ni]==0) continue;
else{
q.push(p(ny,nx));
visit[ny][nx]=1;
}
}
}
}
}
int main(){
int T; cin >> T;
for(int t=1;t<=T;t++){
int r,c,time;
cin >> Y >> X >> r >> c >> time ;
for(int i=0;i<Y;i++){
for(int j=0;j<X;j++){
visit[i][j]=0;
cin >>arr[i][j];
}
}
bfs(r,c,time);
cout << "#"<<t<< " "<<ans <<'\n';
}
}