https://www.acmicpc.net/problem/1654


이분 탐색을 재귀로 구현해보았습니다!

여기서 중요한 것은 mid와 left right를 롱롱형으로 처리한다는 점입니다.

right 초기값을 signed int의 최대값으로 설정했기 때문에 1 + right를 할 경우에

int범위를 벗어나게 됩니다. 그러므로 롱롱형으로 처리를 했습니다.


이 문제도 마찬가지로 무엇을 이분탐색으로 탐색할 것인가??에 대해서 고민하면 쉽게 풀 수 있습니다.

여기서 탐색할 것은 랜선의 길이입니다. 각 랜선에서 몇미터짜리의 랜선으로 자를 것인가!
처음에 최대값부터 시작해서... 이분탐색을 합니다!

임의의 값으로 랜선을 잘랐을 때 랜선의 수가 요구하는 개수보다 많아지면 더 길게!

반대의 경우는 짧게 탐색을 합니다.

조심해야할 점은 문제에서 최대 길이를 요구했으므로

어떤 길이로 잘랐을때 랜선의 개수 N을 만족하더라도 더 긴 길이의 랜선으로 만들어보아야합니다.

예를들어 200으로 잘랐는데도 랜선 N개를 만족할 수도 있고 201도 만족한다면 답은 201이 되어야한다는 말입니다.


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
#include <cstdio>
#define MAX_SIZE 10000
#define INF 0x7fffffff
#define ll long long
int data[MAX_SIZE];
int k, n;
int ret;
 
int binary_search(int key, ll left, ll right)
{
    if(left > right) return -1;
 
    ll mid = (left + right) / 2;
 
    int cnt = 0;
    for(int i = 0; i < k; i++) cnt += data[i] / mid;
 
 
    if(cnt >= key)
    {
        ret = mid > ret ? mid : ret;
        return binary_search(key, mid + 1, right);
    }
    else if(cnt < key) return binary_search(key, left, mid - 1);
 
}
 
int main()
{
 
    scanf("%d %d", &k, &n);
 
    for(int i = 0; i < k; i++) scanf("%d", data + i);
 
    binary_search(n, 1, INF);
 
    printf("%d", ret);
 
    return 0;
}
 
cs


'알고리즘 > 이분 탐색' 카테고리의 다른 글

[2805] 나무 자르기  (3) 2017.04.19
[2512] 예산  (0) 2017.04.19
[2343] 기타 레슨  (0) 2017.04.19
[2110] 공유기 설치  (0) 2017.04.19
[1300] K번째 수  (0) 2017.04.06

https://www.acmicpc.net/problem/2110

이 문제는 저는 개인적으로 꽤 어려웠는데요....

이분 탐색으로 풀 수 있는 문제입니다..

파라메트릭 서치(?)라고.. K번째 수와 마찬가지로 이분 탐색의 응용인 문제인데

집의 수와 공유기의 수 그리고 집의 좌표를 줍니다.


최대한 넓게 넓게 설치해서 인풋으로 요구하는 공유기의 수를 만들어야 하는데..

여기서 어떻게 이분탐색을 하느냐에 대해서 엄청나게 고민했습니다.


결론부터 말하자면! 우리는 거리를 가지고 이분탐색을 해야합니다.


예를 들어 거리를 10으로 첫 시작을 했다면 10간격으로 설치를 해보고 공유기가 더 많이 필요하면 간격을 늘리고

공유기가 덜 설치되었으면 거리를 줄이는 방식으로 이분탐색을 진행하면 됩니다.


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
#include <cstdio>
#include <algorithm>
#define MAX_SIZE 200000
 
int pos[MAX_SIZE];
 
int main()
{
    int n, c;
    scanf("%d %d", &n, &c);
 
    for(int i = 0; i < n; i++) scanf("%d", pos + i);
 
    std::sort(pos, pos + n);
 
    int left = 1, right = pos[n - 1] - pos[0];
    int ret;
 
    while(left <= right)
    {
        int mid = (left + right) / 2;
        int cnt = 1;
        int start = pos[0];
 
        for(int i = 1; i < n; i++)
        {
            if(pos[i] - start >= mid)
            {
                cnt++;
                start = pos[i];
            }
        }
 
        if(cnt >= c)
        {
            ret = mid;
            left = mid + 1;
        }
        else right = mid - 1;
 
    }
 
    printf("%d\n", ret);
 
 
    return 0;
}
 
cs


'알고리즘 > 이분 탐색' 카테고리의 다른 글

[2805] 나무 자르기  (3) 2017.04.19
[2512] 예산  (0) 2017.04.19
[2343] 기타 레슨  (0) 2017.04.19
[1654] 랜선 자르기  (0) 2017.04.19
[1300] K번째 수  (0) 2017.04.06

그냥 문제에 주어진 조건대로 움직이기만 하면 끝나는 문제입니다.

말이 좀 난해하긴한데... 디버깅하면서 따라가니 이해가 가더라구요!

그림 그려보시면 편하실 것 같습니다.


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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <vector>
#include <functional>
 
#define MAX_SIZE 51
#define INF 0x7fffffff
 
using namespace std;
//input
int map[MAX_SIZE][MAX_SIZE];
int m, n;
int sx, sy, sd;
 
//process
int max_value;
int dx[4] = { -1, 0, 1, 0};
int dy[4] = { 0, 1, 0, -1};
 
 
void input()
{
    scanf("%d %d", &m, &n);
    scanf("%d %d %d", &sx, &sy, &sd);
 
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
}
 
int turn(int now, int next)
{
    if(next == 0)//next == 0은 왼쪾으로 턴
    {
        if(now == 0) return 3;
        else if(now == 1) return 0;
        else if(now == 2) return 1;
        else return 2;
    }
    else return (now + 2) % 4;//0->2,2->0,1->3,3->1
}
 
 
void print()
{
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            printf("%d ", map[i][j]);
        }
        puts("");
    }
    puts("");
}
 
void process()
{
    int x = sx;
    int y = sy;
    int d = sd;
    int cnt = 0;
 
    int ret = 1;
    map[x][y] = 2;
 
    int nx;
    int ny;
 
    while(1)
    {
        if(cnt == 4)
        {
            d = turn(d, 1);
            nx = x + dx[d];
            ny = y + dy[d];
 
            if(nx < 0 || ny < 0 || nx >= m || ny >= n || map[nx][ny] == 1) break;
 
            x = nx;
            y = ny;
            d = turn(d, 1);
            cnt = 0;
            continue;
        }
 
        d = turn(d, 0);
        nx = x + dx[d];
        ny = y + dy[d];
 
        cnt++;
 
 
        if(nx < 0 || ny < 0 || nx >= m || ny >= n || map[nx][ny] != 0) continue;
 
        x = nx;
        y = ny;
 
        map[x][y] = 2; // 청소함!
 
        ret++;
        cnt = 0;
    }
 
    printf("%d\n", ret);
}
 
int main()
{
    input();
    process();
 
    return 0;
}
 
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[1941] 소문난 칠공주  (1) 2017.07.01
[2146] 다리 만들기  (2) 2017.05.23
[14502] 연구소  (5) 2017.04.18
[14501] 퇴사  (4) 2017.04.17
[14500] 테트로미노  (0) 2017.04.17

이 문제도 N이 작기 때문에 3개의 기둥을 한번씩 다 세워보고 최대값을 찾는 완전탐색 문제입니다.

dfs는 기둥을 세우는 함수이며, 깊이가 3이 되었을 때(기둥을 세개 세웠을 때) bfs함수를 호출합니다.

bfs는 바이러스가 퍼지는 함수 입니다. bfs가 끝나면 recovery함수를 호출해서 바이러스가 퍼지기 전의 맵 상태로 돌리며,

돌릴 때 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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <vector>
#include <functional>
 
#define MAX_SIZE 8
#define INF 0x7fffffff
 
using namespace std;
//input
int map[MAX_SIZE][MAX_SIZE];
int m, n;
 
//process
bool visit[MAX_SIZE][MAX_SIZE];
int max_value;
int dx[4] = { 1, 0, 0, -1 };
int dy[4] = { 0, 1, -1, 0 };
 
vector<pair<int, int> > virus;
 
void input()
{
    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &map[i][j]);
 
            if(map[i][j] == 2) virus.push_back(make_pair(i, j));
        }
    }
}
 
void copy_map(int (*a)[MAX_SIZE], int (*b)[MAX_SIZE])
{
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            a[i][j] = b[i][j];
        }
    }
}
 
int recovery(int (*a)[MAX_SIZE], int (*b)[MAX_SIZE])
{
    int ret = 0;
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(a[i][j] == 0) ret++;
            a[i][j] = b[i][j];
        }
    }
    return ret;
}
 
void bfs()
{
    queue<pair<int, int> > q;
    for(int i = 0; i < virus.size(); i++) q.push(virus[i]);
 
    while(!q.empty())
    {
        int x = q.front().first;
        int 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 < 0 || ny < 0 || nx >= m || ny >= n || map[nx][ny] != 0) continue;
 
            map[nx][ny] = 2;
            q.push(make_pair(nx, ny));
        }
    }
}
 
void dfs(int x, int y, int d)
{
    map[x][y] = 1;
    visit[x][y] = 1;
 
    if(d == 3)
    {
        //bfs
        int tmp[MAX_SIZE][MAX_SIZE];
        copy_map(tmp, map);
 
        bfs();
        max_value = max(max_value, recovery(map, tmp));
 
        visit[x][y] = 0;
        map[x][y] = 0;
        return;
    }
 
    for(int i = x; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(visit[i][j] || map[i][j] != 0) continue;
            dfs(i, j, d + 1);
        }
    }
 
    map[x][y] = 0;
    visit[x][y] = 0;
}
 
void process()
{
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(map[i][j] != 0) continue;
            dfs(i, j, 1);
        }
    }
 
    printf("%d\n", max_value);
}
 
int main()
{
    input();
    process();
 
    return 0;
}
 
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[2146] 다리 만들기  (2) 2017.05.23
[14503] 로봇 청소기  (2) 2017.04.18
[14501] 퇴사  (4) 2017.04.17
[14500] 테트로미노  (0) 2017.04.17
[3055] 탈출  (0) 2017.04.16

이 문제는.. N이 작아서 그냥 완전 탐색으로 해결했습니다.

결국 그 날에 그 고객을 상담하냐 안하냐 이 두가지 경우 뿐입니다.

굉장히 난이도가 낮은 문제입니다.


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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <vector>
#include <functional>
 
#define MAX_SIZE 16
#define INF 0x7fffffff
 
using namespace std;
//input
int cost[MAX_SIZE];
int day[MAX_SIZE];
int n;
 
//process
int max_value;
 
void input(){
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++) scanf("%d %d", &day[i], &cost[i]);
}
 
void dfs(int d, int sum){
    if (d == n + 1){
        max_value = max(max_value, sum);
        return;
    }
 
    if(d + day[d] <= n + 1) dfs(d + day[d], sum + cost[d]);
    if(d + 1 <= n + 1) dfs(d + 1, sum);
}
 
void process(){
    dfs(1, 0);
    printf("%d\n", max_value);
}
 
int main(){
    input();
    process();
 
    return 0;
}
cs



디피로도 한번 풀어봤는데..

더 효율적인 점화식이 있다면 댓글 부탁드립니다.


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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <vector>
#include <functional>
 
#define MAX_SIZE 51
#define INF 0x7fffffff
 
using namespace std;
 
int day[MAX_SIZE];
int cost[MAX_SIZE];
int dp[MAX_SIZE];
 
int main(){
 
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d %d", &day[i], &cost[i]);
 
    int ret = 0;
    for(int i = 1; i <= n; i++){
        int next1 = i + day[i];
        int next2 = i + 1;
 
        if(next1 <= n + 1) dp[next1] = max(dp[next1], dp[i] + cost[i]);
        if(next2 <= n + 1) dp[next2] = max(dp[next2], dp[i]);
 
        ret = max(max(ret, dp[next1]), dp[next2]);
    }
 
    printf("%d\n", ret);
 
    return 0;
}
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[14503] 로봇 청소기  (2) 2017.04.18
[14502] 연구소  (5) 2017.04.18
[14500] 테트로미노  (0) 2017.04.17
[3055] 탈출  (0) 2017.04.16
[5427] 불  (0) 2017.04.16

음... 테트리스의 모양 중에서 다른건 간단하게 생각하셨을 것 같은데...

凸이 모양이 좀 고민스러웠죠...

저는

위, 아래, 왼, 오른쪽으로 각각 가중치를 주었습니다. dfs 매개변수에서 weight라는 변수입니다.

위 = 1

아래 = 10

왼 = 100

오 = 1000

이렇게 각각 주어서

만약 세로로 세칸 짜리는 20이 될 것입니다.(0부터 시작하므로 2칸이동하면 20)

만약 가로로 세칸 짜리는 2000이 될 것입니다. 오른쪽으로 두 칸 갔기 때문입니다.

이 두가지 경우에는 추가로 2방향씩 더 검사해줍니다.

세로 방향일 경우에는 1시와 11시 대각선을 검사하고, (코드에서 (ddx[0], ddy[0]), (ddx[1], ddy[1]))

가로 방향일 경우에는 11시와 7시 방향의 대각선을 검사하면 됩니다. (코드에서 (ddx[2], ddy[2]), (ddx[3], ddy[3]))

모든 맵을 dfs하고 가장 큰 수를 출력하면 끝입니다.!


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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <string.h>
#include <vector>
#include <functional>
 
#define MAX_SIZE 500
#define INF 0x7fffffff
 
using namespace std;
//input
int map[MAX_SIZE][MAX_SIZE];
int m, n;
 
//process
bool visit[MAX_SIZE][MAX_SIZE];
int max_value;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int ddx[4] = { -1, -1, -1, 1 };
int ddy[4] = { -1, 1, -1, -1 };
 
void input(){
    scanf("%d %d", &m, &n);
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            scanf("%d", &map[i][j]);
        }
    }
}
 
int pow(int n, int r){
    if (r == 0) return 1;
    else if (r % 2 == 0){
        int tmp = pow(n, r / 2);
        return tmp *tmp;
    }
    else return pow(n, r - 1) * n;
}
 
void dfs(int x, int y, int d, int sum, int weight){
    if (d == 3){
        max_value = max(max_value, sum);
        return;
    }
 
    for (int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if (nx < 0 || ny < 0 || nx >= m || ny >= n || visit[nx][ny]) continue;
 
        visit[x][y] = 1;
 
        dfs(nx, ny, d + 1, sum + map[nx][ny], weight + pow(10, i));
 
        visit[x][y] = 0;
    }
 
    if (weight == 20){
        for (int i = 0; i < 2; i++){
            int nx = x + ddx[i];
            int ny = y + ddy[i];
 
            if (nx < 0 || ny < 0 || nx >= m || ny >= n || visit[nx][ny]) continue;
 
            dfs(nx, ny, d + 1, sum + map[nx][ny], weight);
        }
    }
    else if (weight == 2000){
        for (int i = 2; i < 4; i++){
            int nx = x + ddx[i];
            int ny = y + ddy[i];
 
            if (nx < 0 || ny < 0 || nx >= m || ny >= n || visit[nx][ny]) continue;
 
            dfs(nx, ny, d + 1, sum + map[nx][ny], weight);
        }
    }
 
}
 
void process(){
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            dfs(i, j, 0, map[i][j], 0);
        }
    }
    printf("%d\n", max_value);
}
 
int main(){
    input();
    process();
 
    return 0;
}
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[14502] 연구소  (5) 2017.04.18
[14501] 퇴사  (4) 2017.04.17
[3055] 탈출  (0) 2017.04.16
[5427] 불  (0) 2017.04.16
[13460] 째로탈출2  (2) 2017.04.16

https://www.acmicpc.net/problem/3055


이전의 글 중에서.. 불이라는 문제가 있는데요!!
그 문제랑 완전히 똑같다고 보시면됩니다!!!!!

bfs연습하기 좋을것 같군요!


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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
 
#define MAX_SIZE 51
 
using namespace std;
 
typedef struct _data
{
    int x;
    int y;
    int sec;
    bool water;
} data;
 
int r, c;
char map[MAX_SIZE][MAX_SIZE];
bool visit[MAX_SIZE][MAX_SIZE];
int startx, starty;
int endx, endy;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
vector<pair<int, int> > w;
 
//고슴도치 S
//동굴 D
//X는 벽
//*는 물
void input()
{
    scanf("%d %d", &r, &c);
    getchar();
 
    for(int i = 0; i < r; i++)
    {
        for(int j = 0; j < c; j++)
        {
            scanf("%c", &map[i][j]);
 
            if(map[i][j] == 'S')
            {
                startx = i;
                starty = j;
            }
            else if(map[i][j] == 'D')
            {
                endx = i;
                endy = j;
            }
            else if(map[i][j] == '*')
            {
                w.push_back(make_pair(i, j));
            }
        }
        getchar();
    }
}
 
int bfs()
{
    queue<data> q;
    for(int i = 0; i < w.size(); i++) q.push(data{w[i].first, w[i].second, 0, 1});
    q.push(data{startx, starty, 0, 0});
 
    while(!q.empty())
    {
        data pop_data = q.front();
        q.pop();
 
        int x = pop_data.x;
        int y = pop_data.y;
        int t = pop_data.sec;
        bool water = pop_data.water;
 
        if(water == 0 && endx == x && endy == y) return t;
 
        if(!water && visit[x][y] == 1) continue;
        else if(!water && visit[x][y] == 0) visit[x][y] = 1;
 
 
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if(nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
            if(map[nx][ny] == 'X' || map[nx][ny] == '*') continue;
            if(water && map[nx][ny] == 'D') continue;
            if(water) map[nx][ny] = '*';
            q.push(data{nx, ny, t + 1, water});
        }
    }
 
    return -1;
}
 
int main()
{
    input();
    int ret = bfs();
    if(ret == -1) puts("KAKTUS");
    else printf("%d\n", ret);
 
 
 
    return 0;
}
 
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[14501] 퇴사  (4) 2017.04.17
[14500] 테트로미노  (0) 2017.04.17
[5427] 불  (0) 2017.04.16
[13460] 째로탈출2  (2) 2017.04.16
[12100] 2048 easy  (0) 2017.04.16

https://www.acmicpc.net/problem/5427


이 문제는 ..전형적인 BFS문제라고 할 수 있습니다..


제 주변에 큐를 두개를 써서 푸시는 분들이 꽤 계신데..


저는 큐를 하나를 썼습니다.

하나를 쓸 때 핵심은 불을 먼저 넣고 사람을 넣어야한다는 점입니다.

이유는 사람을 먼저 넣을 경우 불이 퍼지는 위치임을 알지 못하고 불에 휩싸여 죽을 수가 있기 때문입니다!

BFS탈출 조건은.. 맵의 가장자리에 도착하면 탈출한 것임으로.. 끝나겠죠!?!?!?


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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
#define MAX_SIZE 1000
 
using namespace std;
 
typedef struct
{
    int x;
    int y;
    int sec;
    bool type;
} pos;
 
vector<pair<int, int> > v;//fire_pos
 
bool visit[MAX_SIZE][MAX_SIZE];
char map[MAX_SIZE][MAX_SIZE];
int n, m;
int sx, sy;
 
void input()
{
    scanf("%d %d", &n, &m);
    getchar();
 
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            char c = getchar();
            map[i][j] = c;
            if(c == '*') v.push_back(make_pair(i, j));
            else if(c == '@') sx = i, sy = j;
        }
        getchar();
    }
}
 
int bfs()
{
    queue<pos> q;
 
    for(int i = 0; i < v.size(); i++) q.push(pos{v[i].first, v[i].second, 0, 0});
    q.push(pos{sx, sy, 0, 1});
 
    visit[sx][sy] = 1;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
 
    while(!q.empty())
    {
        pos pop_data = q.front();
        q.pop();
 
        int x = pop_data.x;
        int y = pop_data.y;
        int sec = pop_data.sec;
        int type = pop_data.type;
 
        if(type && (x == 0 || x == m - 1|| y == 0 || y == n - 1)) return sec + 1;
 
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
            if(map[nx][ny] == '#' || map[nx][ny] == '*') continue;
            if(visit[nx][ny]) continue;
 
            if(type) visit[nx][ny] = 1;
            else map[nx][ny] = '*';
 
            q.push(pos{nx, ny, sec + 1, type});
        }
    }
 
    return 0;
}
 
void print()
{
    for(int i = 0; i < m; i++) printf("%s\n", map[i]);
}
 
int main()
{
    int t;
    scanf("%d", &t);
 
    for(int test_case = 0; test_case < t; test_case++)
    {
        v.clear();
        memset(visit, 0, sizeof(visit));
 
        input();
 
        int ret = bfs();
        if(ret) printf("%d\n", ret);
        else printf("IMPOSSIBLE\n");
    }
 
    return 0;
}
 
 
 
 
cs


'알고리즘 > 탐색' 카테고리의 다른 글

[14500] 테트로미노  (0) 2017.04.17
[3055] 탈출  (0) 2017.04.16
[13460] 째로탈출2  (2) 2017.04.16
[12100] 2048 easy  (0) 2017.04.16
[5214] 환승  (0) 2017.04.04

+ Recent posts

티스토리툴바