Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- c#
- Stack 이란
- 백준
- 게리멘더링2
- 구현
- ㅣ풀이
- dfs
- 백준 5397
- 스택의 특징
- AVL 시간 복잡도
- 해시 구현
- 자료구조
- heap
- 시간 복잡도
- 백준 1158
- 백준 17822
- 백준 1406
- 풀이
- 5397
- 1764
- 원판 돌리기
- 백준 17779
- qorwns
- 별 찍기 10
- C/C++ 구현
- 해시구현
- 버킷 정렬
- 백준 2447
- 조세퍼스 순열
- 백준 17471
Archives
- Today
- Total
홍시홍의 프로그래밍
[swea 1953] 탈주범 검거 본문
분류
구현
요구사항
탈주범이 제한시간 동안 이동할 수 있는 파이프 수 구하기
풀이
기본적으로 bfs로 구현한다
조건은 현재 -> 다음 파이프로 이동할때 가능한가 확인한다
가능 하다면 visit +1 을 해준다
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
int n, m, r, c,l;
int map[55][55];
int visit[55][55];
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
int ans = 0;
bool check(int dir,int next) {
if (dir == 0) {
if (next == 1 || next == 2 || next == 5 || next == 6)
return true;
}
else if (dir == 1) {
if (next == 1 || next == 3 || next == 4 || next == 5)
return true;
}
else if (dir == 2) {
if (next == 1 || next == 2 || next == 4 || next == 7)
return true;
}
else if (dir == 3) {
if (next == 1 || next == 3 || next == 6 || next == 7)
return true;
}
return false;
}
void solve() {
memset(visit, 0, sizeof(visit));
queue<pair<int, int>> q;
q.push({ r,c });
visit[r][c] = 1;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
int now = map[x][y];
q.pop();
for (int i = 0; i < 4; i++) {
int nr = x + dr[i];
int nc = y + dc[i];
if (nr < 0 || nc < 0 || nr >= n || nc >= m)
continue;
if (visit[nr][nc] == 0) {
int next = map[nr][nc];
if (now == 1) {
if (check(i, map[nr][nc])) {
visit[nr][nc] = visit[x][y]+1;
q.push({ nr,nc });
}
}
else if (now == 2) {
if (i == 0 || i == 2) {
if (check(i, next)) {
visit[nr][nc] = visit[x][y] + 1;
q.push({ nr,nc });
}
}
}
else if (now == 3) {
if (i == 1 || i == 3) {
if (check(i, next)) {
visit[nr][nc] = visit[x][y] + 1;
q.push({ nr,nc });
}
}
}
else if (now == 4) {
if (i == 0 || i == 3) {
if (check(i, next)) {
visit[nr][nc] = visit[x][y] + 1;
q.push({ nr,nc });
}
}
}
else if (now == 5) {
if (i == 3 || i == 2) {
if (check(i, next)) {
visit[nr][nc] = visit[x][y] + 1;
q.push({ nr,nc });
}
}
}
else if (now == 6) {
if (i == 1 || i == 2) {
if (check(i, next)) {
visit[nr][nc] = visit[x][y] + 1;
q.push({ nr,nc });
}
}
}
else if (now == 7) {
if (i == 1 || i == 0) {
if (check(i, next)) {
visit[nr][nc] = visit[x][y] + 1;
q.push({ nr,nc });
}
}
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (visit[i][j]!=0 &&visit[i][j] <= l) {
ans++;
}
//cout << visit[i][j] << " ";
}
//cout << endl;
}
}
int main() {
int t;
scanf("%d", &t);
for (int tc = 1; tc <= t; tc++) {
ans = 0;
scanf("%d%d%d%d%d", &n, &m, &r, &c, &l);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &map[i][j]);
}
}
solve();
printf("#%d %d\n", tc, ans);
}
}
'알고리즘 문제풀이 > swea' 카테고리의 다른 글
[swea 4012] 요리사 (0) | 2020.06.05 |
---|---|
[swea 1949] 등산로 조성 (0) | 2020.04.25 |
[swea 5650] 핀볼 게임 (0) | 2020.04.24 |
[swea 2117] 홈 방범 서비스 (0) | 2020.04.24 |
[swea 2112] 보호 필름 (0) | 2020.04.24 |