How We Coding

<5-8> 전체탐색 - 미로 만드는 사람 (MazeMaker)

PS/Topcoder training2018. 7. 16. 12:26

### 전체탐색 ###


### SRM 433.5 Div2 Level 2 ###


<소스코드>


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 <vector>
#include <queue>
#include <string>
using namespace std;
 
int rSize, cSize;
int visited[51][51];
 
struct P { 
    int r, c; 
    P(int r, int c) : r(r), c(c) {}
};
 
bool safe(int r, int c)
{
    return (0 <= r && r < rSize) && (0 <= c && c < cSize);
}
 
class MazeMaker {
public:
    int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol) {
        rSize = maze.size();
        cSize = maze[0].size();
               
        P cur(startRow, startCol);
        visited[startRow][startCol] = 1;
        
        queue<P> q;
        q.push(cur);
 
        while(!q.empty()) {
            int curR = q.front().r;
            int curC = q.front().c; q.pop();
 
            int sz = moveRow.size();
            for(int k=0; k<sz; k++) {
                int nr = curR + moveRow[k];
                int nc = curC + moveCol[k];
                if(safe(nr, nc) && maze[nr][nc] == '.' && !visited[nr][nc]) {
                    P tmp(nr, nc);
                    q.push(tmp);
                    visited[nr][nc] = visited[curR][curC]+1;
                }
            }
        }
        int ans = 0;
        for(int r=0; r<rSize; r++) {
            for(int c=0; c<cSize; c++) {
                if(maze[r][c] == '.' && visited[r][c] == 0) return -1;
                if(maze[r][c] == '.' && ans < visited[r][c]) {
                    ans = visited[r][c];
                }
            }
        }
        return ans-1;
    }
};
 
cs


>> 방문할 수 있는 모든 곳을 탐색. 방문을 못한 곳이 있으면 -1; 모두 방문했다면, 방문한 곳중 가장 먼 곳이 정답.

'PS > Topcoder training' 카테고리의 다른 글

<5-9> 전체탐색 - 마법의 숫자 (NumberMagicEasy)  (0) 2018.07.16
<8-8> 수학 - 둥근 모양의 국가들 (CirclesCountry)  (0) 2018.07.16
<8-4> 그리디 - 배치 시스템 (BatchSystem)  (0) 2018.07.16
<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04

<8-8> 수학 - 둥근 모양의 국가들 (CirclesCountry)

PS/Topcoder training2018. 7. 16. 11:15

### 수학 ###


### SRM 443 Div2 Level 2 ###



<소스트리>


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <vector>
using namespace std;
 
double dist(int x1, int y1, int x2, int y2)
{
    return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
}
 
class CirclesCountry {
public:
    int leastBorders(vector <int> X, vector <int> Y, vector <int> R, int x1, int y1, int x2, int y2) {
        
        int ans=0;
        for(int i=0; i<X.size(); i++) {
            double d1 = dist(X[i], Y[i], x1, y1);
            double d2 = dist(X[i], Y[i], x2, y2);
            double r = (double)R[i]*R[i];
            if(d1 < r) ans++;
            if(d2 < r) ans++;
            if(d1 < r && d2 < r) ans -= 2;
        }
        return ans;
    }
};
cs


>>> 기본 아이디어는 시작 좌표와 목표 좌표가 둥근성에 포함되어 있으면 카운트.

>>> 예외처리 : 같은 성에 동시에 포함되어 있으면 카운트하면 안된다.

'PS > Topcoder training' 카테고리의 다른 글

<5-9> 전체탐색 - 마법의 숫자 (NumberMagicEasy)  (0) 2018.07.16
<5-8> 전체탐색 - 미로 만드는 사람 (MazeMaker)  (0) 2018.07.16
<8-4> 그리디 - 배치 시스템 (BatchSystem)  (0) 2018.07.16
<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04

<8-4> 그리디 - 배치 시스템 (BatchSystem)

PS/Topcoder training2018. 7. 16. 01:54

### Greedy ###


### SRM 481 Div2 Level 3 ###


<소스코드>


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
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
 
typedef long long int lli;
 
struct P { 
    int i, duration; 
    P(int i, int duration) : i(i), duration(duration) {}
};
 
struct userInfo {
    vector<P> v;
    lli sum;
    userInfo(vector<P> v, lli sum) : v(v), sum(sum) {}
};
 
bool cmp(P a, P b)
{
    return a.i < b.i;
}
 
bool cmp2(userInfo a, userInfo b)
{
    return a.sum != b.sum ? a.sum < b.sum : a.v[0].i < b.v[0].i;
}
    
class BatchSystem {
public:
    vector<int> schedule(vector <int> duration, vector <string> user) {
        int userIdx=0;
        map<string, int> msi;
        vector<userInfo> info;
        for(int i=0; i<duration.size(); i++) {
            if(msi.find(user[i]) == msi.end()) {
                msi[user[i]] = ++userIdx;
                vector<P> v; v.push_back(P(i, duration[i]));
                info.push_back(userInfo(v, duration[i]));
            }
            else {
                int idx = msi[user[i]]-1;
                info[idx].sum += duration[i];
                info[idx].v.push_back(P(i, duration[i]));
            }
        }
            
        for(int i=0; i<info.size(); i++) {
            sort(info[i].v.begin(), info[i].v.end(), cmp);
        }
 
        sort(info.begin(), info.end(), cmp2);
        
        vector<int> ans;
        for(int i=0; i<info.size(); i++) {
            for(int j=0; j<info[i].v.size(); j++) {
                ans.push_back(info[i].v[j].i);
            }
        }
        return ans;
    }
};
 
cs


'PS > Topcoder training' 카테고리의 다른 글

<5-8> 전체탐색 - 미로 만드는 사람 (MazeMaker)  (0) 2018.07.16
<8-8> 수학 - 둥근 모양의 국가들 (CirclesCountry)  (0) 2018.07.16
<8-1> 탐색범위 한정 - 다양한 색상의 상자와 공 (ColorfulBoxesAndBalls)  (0) 2018.07.14
<7-5> DP - 악수 (HandShaking)  (0) 2018.07.04
<5-7> 전체탐색 - 고장난 로봇 (CrazyBot)  (0) 2018.07.03

티스토리툴바