\ # 우 객 망 2018 년 우 객 다 교 알고리즘 겨울방학 훈련소 연습 경기 (제4 회) 도 론 + 지도 검색 문제 풀이

A - 석유 채집
제목 설명
해상 운송 u 의 석유 유출 문제 에 따라 새로운 이익 이 있 는 업계 가 탄생 하고 있 는데 그것 이 바로 기름 을 버 리 는 업계 이다.현재 멕시코 만 에 떠 다 니 는 대량의 석유 가 많은 상인 들 의 눈길 을 끌 고 있다.이 상인 들 은 해수면 전 체 를 20 미터 건 너 10 미터 정도 되 는 긴 사각형 을 탈 수 있 는 특별한 비행 기 를 가지 고 있다.(상하 가 인접 하거나 좌우 가 인접 한 칸 은 기울 여 서 는 안 된다) 물론 한 바 가 지 를 버 리 는 것 은 모두 기름 이다. 한 바 가 지 는 기름 에 물이 있 으 면 의미 가 없고 자원 을 이용 할 수 없다.지금 상인 들 은 이 지역 에서 기름 을 얼마나 많이 얻 을 수 있 는 지 알 고 싶 어 한다.

     N×N   ，      10m×10m      ，               

입력 설명:

            
                  T（T<75）
          N（N<50）          ，   N ，    N   ，    ’.’    、  ’#’    。

출력 설명:

      “Case X: M”（X 1  ），M            。

예시 1
입력
 

1
6
......
.##...
......
.#..#.
.#..##
......

출력
 

Case 1: 3

제목: 두 개의 인접 한 칸 을 연속 으로 1 바가지 크기 로 하고, 기름 을 가 져 간 후 남 은 두 조각 은 해수면 에서 취 할 수 없 는 것 이 되 며, 수출 은 최대 몇 바 가 지 를 취 할 수 있 습 니까?
사고: 연결 블록 문제 와 유사 하 게 하 나 를 홀수 점 으로 설정 하고 하 나 를 짝수 점 으로 설정 하 며 '\ #' 에 부 딪 힐 때마다 지 도 를 검색 하고 검색 한 곳 을 '' 로 설정 합 니 다. 매번 홀수 점 과 짝수 점 의 최소 값 의 합 을 더 하면 답 입 니 다.
AC 코드:

#include
using namespace std;
const int maxn = 1e2 + 5;

char p[maxn][maxn];
int n, m, odd, even, T, X;
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
void dfs(int x, int y, int step) {
    if (step & 1) even++;
    else odd++;
    for (int i = 0; i < 4; i++) {
        int xx = dir[i][0] + x;
        int yy = dir[i][1] + y;
        if (xx >= 0 && yy >= 0 && xx < n && yy < n && p[xx][yy] == '#') {
            p[xx][yy] = '.';
            dfs(xx, yy, step + 1);
        }
    }
}

int main()
{
    cin >> T;
    while (T--) {
        cin >> n;
        int ans = 0;
        for (int i = 0; i < n; i++) cin >> p[i];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (p[i][j] == '#') {
                    odd = even = 0;
                    p[i][j] = '.';
                    dfs (i, j, 0);
                    ans += min (odd, even);
                }
            }
        }
        cout << "Case " << ++X << ": ";
        cout << ans << endl;
    }
    return 0;
}

 
B - 도로 건설
 
제목 설명
현재 사회의 변화 에 따라 교통 문제 도 점점 중요 해 지기 때문에 시장 은 각 도시 간 의 무역 과 거래 를 편리 하 게 하기 위해 도 로 를 건설 하기 로 결정 했다.시장의 생각 은 좋 지만 일반인 들 도 자주 골 치 아 픈 문제 에 부 딪 혔 다. 그것 은 바로 수중 에 있 는 경비 가 제한 되 어 있다 는 것 이다. 계획 과정 에서 디자이너 들 은 일부 도시 간 에 도 로 를 건설 하 는 경비 수 요 를 예산 해 냈 다.현재 시장 은 그것 이 그의 m 개 도 시 를 제 한 된 경비 내 에서 도로 교통 을 실현 할 수 있 는 지 궁금 하 다.가능 하 다 면 Yes 를 출력 하 십시오. 그렇지 않 으 면 No 를 출력 합 니 다.
입력 설명:

            
        1          c(<1000000)，    n(n<10000)，      m(<100)。
    n            ，        ，          v1、v2(0

출력 설명:

       ，  Yes No。

예시 1
입력
 

20 10 5
1 2 6
1 3 3
1 4 4
1 5 5
2 3 7
2 4 7
2 5 8
3 4 6
3 5 9
4 5 2

출력
 

Yes

예시 2
입력
 

10 2 2
1 2 5
1 2 15

출력
 

Yes

비고:

 사고: 누 드 의 최소 생 성 트 리 입 니 다. 저 는 크 루 스 칼 알고리즘 을 사용 합 니 다. 매번 가장 짧 은 변 을 찾 을 때마다 새로 추 가 된 두 점 이 집합 에 가입 하지 않 았 는 지, 추가 하 는 지, 건 너 뛰 는 지, 마지막 으로 가중치 가 일치 하 는 지 확인 하 겠 습 니 다.
AC 코드:

#include
using namespace std;
const int maxn = 1e4 + 5;

struct node
{
    int u, v, w;
}e[maxn];
bool cmp (node a, node b) {
    return a.w < b.w;
}
int p[maxn], n, m, c, ans, K;
void init() {
    memset(e, 0, sizeof(e));
    for (int i = 1; i <= n; i++) p[i] = i;
    ans = K = 0;
}
int find_(int x) {
    while (x != p[x]) x = p[x] = p[p[x]];
    return x;
}
void unite(int x, int y) {
    x = find_(x);
    y = find_(y);
    if (x != y) p[x] = y;
}

int main()
{
    while (cin >> c >> m >> n) {
        init();
        for (int i = 0; i < m; i++)
            cin >> e[i].u >> e[i].v >> e[i].w;
        sort (e, e + m, cmp);
        for (int i = 0; i < m; i++) {
            if (K == n - 1) break;
            if (find_(e[i].u) != find_(e[i].v)) {
                unite(e[i].u, e[i].v);
                ans += e[i].w;
                K++;
            }
        }
        if (K == n - 1 && ans <= c) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

 
 C - 교차
 
제목 설명

           ，         。

 
입력 설명:

       ，       。
         ：
         n,m(0

출력 설명:

                        （             ），        "empty"。

예시 1
입력
 

2 3
1 3
1 2 3

출력
 

1 3

비고:

        ，  "empty"
。

제목 대의: 두 집합의 공공 요 소 를 구하 다
사고방식: 이분법 으로 순서대로 찾 으 면 됩 니 다. lower 로bound 가 제출 하면 TLE 가 될 수 있 습 니 다. 직접 손 으로 쓰 면 지나 갑 니 다.
AC 코드:

#include
using namespace std;
const int maxn = 1e6 + 5;

int p[maxn], s[maxn], n, m;

int main()
{
    while (~scanf("%d%d", &n, &m)) {
        bool flag = 0;
        for (int i = 0; i < n; i++) scanf("%d", &p[i]);
        for (int i = 0; i < m; i++) scanf("%d", &s[i]);
        for (int i = 0; i < n; i++) {
            int l = 0, r = m - 1, mid;
            while (l <= r) {
                mid = (l + r) >> 1;
                if (s[mid] > p[i]) r = mid - 1;
                else if (s[mid] < p[i]) l = mid + 1;
                if (s[mid] == p[i]) {flag = 1; break;}
            }
            if (flag) cout << p[i] << " ";
        }
        if (flag) cout << endl;
        else cout << "empty" << endl;
    }
    return 0;
}

 
D - 샤 오 밍 의 광산 발굴 여행
 
제목 설명

               n*m      ，        。                        。                  ，             ，        。           ，               。  ，      ，                。                   ，                                     。             ，                     。                                ，             。

 
입력 설명:

       。
       ：
         n m（0

출력 설명:

    。        ，               。

예시 1
입력
 

3 3
...
.#.
...

출력
 

1

사고: 제목 의 뜻 을 이해 하지 못 했 습 니 다. 다른 사람의 설명 을 보면 첫 번 째 점 에서 직접 검색 하 는 것 이 라 고 합 니 다. 장애 에 부 딪 히 면 + 1 (QAQ 는 정말 모 르 겠 습 니 다)
AC 코드:

#include
using namespace std;
char mp[1004][1004];
int main()
{
    int n, m, i, j;
    while(~scanf("%d%d", &m, &n))
    {
        int ans = 0, sum = 0;
        for(i = 0; i < m; i++) scanf("%s", mp[i]);
        for(i = 0; i < m ; i++)
            for(j = 0; j < n; j++)
            {
                if(mp[i][j] == '.')
                {
                    sum++;
                    if((mp[i+1][j] == '#' || i == m-1) && (mp[i][j+1] == '#' || j == n-1))
                        ans++;
                }
            }
        if(sum == 1) ans = 0;
        printf("%d
", ans);
    }
    return 0;
}

 
E - 동생 에 게 알 리 기
 
제목 설명
        전쟁 시기 에 A 국 은 많은 간첩 을 다른 나라 에 보 내 정 보 를 수집 했다.스파이 는 자신의 신분 을 비밀 로 해 야 하기 때문에 그들 사 이 는 일방적인 관계 일 뿐이다.그래서 어떤 스파이 는 일부 스파이 에 게 만 연락 할 수 있다.스파이 도 그 와 연락 한 사람 이 누 군지 모른다.HA 는 스파이 들 의 맏형 이지 만, 그 역시 일부 스파이 에 게 만 연락 할 수 있 었 다.하 는 지금 모든 스파이 에 게 알 리 라 는 명령 이 있 습 니 다.하 는 그 가 연락 할 수 있 는 스파이 를 몇 명 이라도 알려 줘 야 모든 스파이 에 게 알 릴 수 있 는 지 알 고 싶 어 한다.
입력 설명:

       。
        ：
        n，m（0

출력 설명:

    ，        ，  HA          。  HA         ，  -1。

예시 1
입력
 

3 2
1 2
1 2
1 1
0

출력
 

-1

예시 2
입력
 

3 1
1
2 2 3
0
0

출력
 

1

 제목: 당신 이 알 릴 수 있 는 사람 을 입력 하고 방향 도 를 입력 하 세 요. U  V 는 U 가 V 에 연락 할 수 있 음 을 표시 합 니 다. 출력 은 최소 몇 명 에 게 알려 야 모든 사람 에 게 알려 줄 수 있 습 니까? 모든 사람 에 게 알 리 지 못 하면 출력 - 1
사고: 먼저 줄 이 고 새 그림 에서 입 도 를 0 으로 하 는 점 을 찾 습 니 다. 입 도 는 0 이기 때문에 '알려 져 야 합 니 다'. 모든 입 도 를 0 으로 하 는 점 이 처음에 입력 한 숫자 에 있 는 지 확인 하고 알 리 지 못 하 는 것 이 있 으 면 출력 - 1
AC 코드:

#include
using namespace std;
const int maxn = 1e6 + 5;

struct node
{
    int v, next;
}e[maxn];
int dfn[maxn], low[maxn], in[maxn], n, m, t, vi;
int head[maxn], suo[maxn], pre[maxn], cnt, tot, scnt;
bool vis[maxn];
stack  st;
map  mp;
void init() {
    memset(in, 0, sizeof(in));
    memset(vis, 0, sizeof(vis));
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(suo, 0, sizeof(suo));
    memset(head, -1, sizeof(head));
    tot = scnt = cnt = 0;
}
void add (int from, int to) {
    e[++cnt].v = to;
    e[cnt].next = head[from];
    head[from] = cnt;
}
void tarjan(int x) {
    dfn[x] = low[x] = ++tot;
    st.push(x);
    vis[x] = 1;
    for (int i = head[x]; i != -1; i = e[i].next) {
        int v = e[i].v;
        if (!dfn[v]) {
            tarjan(v);
            low[x] = min (low[x], low[v]);
        }
        else if (vis[v]) low[x] = min (low[x], dfn[v]);
    }
    if (dfn[x] == low[x]) {
        scnt++;
        int k;
        do {
            k = st.top();
            st.pop();
            suo[k] = scnt;
            vis[k] = 0;
        }
        while (k != x);
    }
}

int main()
{
    while (cin >> n >> m) {
        init();
        for (int i = 0; i < m; i++) {
            cin >> t;
            mp[t]++;   //       
        }
        for (int i = 1; i <= n; i++) {
            cin >> t;
            while (t--) {
                cin >> vi;
                add (i, vi);   //  
            }
        }
        for (int i = 1; i <= n; i++) {
            if (!dfn[i]) tarjan(i);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = head[i]; j != -1; j = e[j].next) {
                int u = suo[i], v = suo[e[j].v];
                if (u != v) in[v]++;   //      
            } 
        }
        int ans = 0, flag = 1;
        for (int i = 1; i <= scnt; i++) {
            if (!in[i]) {
                bool ma = 0;
                for (auto it : mp) {
                    if (suo[it.first] == i) {ma = 1; break;}  
                }
                if (ma) ans++;  
                else {flag = 0; break;}   //        -1
            }
        }
        if (!flag) cout << -1 << endl;
        else cout << ans << endl;
        mp.clear();   //     
    }
    return 0;
}

 
F-Call to your teacher
 
 
제목 설명
실험실 에서 나 온 후, 너 는 갑자기 자신의 컴퓨터 를 실험실 에 두 고 온 것 을 발견 하 였 으 나, 실험실 의 선생님 은 이미 대문 을 잠 갔다.더 나 쁜 것 은 네가 그 선생님 의 전화번호 가 없다 는 것 이다.당신 은 당신 이 아 는 모든 사람 에 게 전 화 를 걸 어 선생님 의 전화 가 있 는 지 물 어보 기 시 작 했 습 니 다. 없 으 면 그들 도 자신의 학우 에 게 전화 번 호 를 물 어 볼 것 입 니 다.그럼 선생님 께 연락 해서 컴퓨터 를 받 을 수 있 습 니까?
입력 설명:

        
               n(1

출력 설명:

        ，           ，  “Yes”，    “No”。

예시 1
입력
 

5 5
1 3
2 3
3 4
2 4
4 5

출력
 

Yes

예시 2
입력
 

4 3
1 2
2 3
4 1

출력
 

No

제목: 당신 의 번 호 는 1 이 고 선생님 의 번 호 는 N 입 니 다. 도표 에 U 를 표시 하 는 것 을 입력 하 십시오.  통지 할 수 있다  V, 1 부터 N 까지 가능 한 지 물 어보 세 요.
사고방식: 직접 dijkstra 를 한 번 걸 어가 서 1 부터 N 까지 길이 있 는 지 확인 하면 됩 니 다.
AC 코드:

#include
using namespace std;
const int maxn = 1e4 + 5;
const int INF = 0x3f3f3f3f;

struct node
{
    int v, w, next;
}e[maxn];
struct edge
{
    int id, w;
    bool operator < (const edge &oth) const
    {
        return w > oth.w;
    }
}mid;
int head[maxn], dis[maxn], n, m, cnt;
priority_queue  q;
void init() {
    memset(e, 0, sizeof(e));
    memset(head, -1, sizeof(head));
    cnt = 0;
}
void add (int from, int to, int dis) {
    e[++cnt].v = to;
    e[cnt].w = dis;
    e[cnt].next = head[from];
    head[from] = cnt;
}
void dijkstra(int u) {
    memset(dis, INF, sizeof(dis));
    dis[u] = 0;
    q.push({u, 0});
    while (!q.empty()) {
        mid = q.top();
        q.pop();
        int ans = mid.id;
        if (mid.w != dis[ans]) continue;
        for (int i = head[ans]; i != -1; i = e[i].next) {
            if (dis[e[i].v] > dis[ans] + e[i].w) {
                dis[e[i].v] = dis[ans] + e[i].w;
                q.push({e[i].v, dis[e[i].v]});
            }
        }
    }
}

int main()
{
    while (cin >> n >> m) {
        init();
        for (int i = 0; i < m; i++) {
            int ui, vi;
            cin >> ui >> vi;
            add (ui, vi, 1);
        }
        dijkstra(1);
        if (dis[n] != INF) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

 G - 노자 의 이탈리아 포 네요.
 
제목 설명
태원 현성 을 공격 한 후 이 운 룡 이라는 이탈리아 포 는 더욱 순조롭게 사용 되 었 다. 어디 를 때 려 도 결코 모호 하지 않다 는 뜻 이다. 그래서 소 야 대장 은 독립 단 포병 영 을 미 친 듯 이 공격 하기 시작 했다. 병사 들 이 이탈리아 포 를 이동 하 는 능력 을 단련 하기 위해 이 단장 은 포병 영 에 특 훈 을 실시 하기 시작 했다.포탄 세 부분 으로 이 뤄 져 현재 이 단장 은 양 촌 에 진 지 를 두 고 각각 포신, 바퀴, 포탄 을 세 곳 에 두 고 있 으 며, 각 부분의 무게 가 다 르 기 때문에 수송 속도 도 다르다.단장 은 누가 이 태 리 포 를 가장 빨리 조립 해서 내 앞 에 운반 할 수 있 는 능력 이 있 습 니까? 아버 지 는 그 에 게 고구마 반 근 을 주 셨 습 니 다. 스님 은 듣 고 기뻐 하 셨 습 니 다. 그런데 그 는 어떻게 해 야 시간 을 가장 빨리 할 수 있 는 지 모 르 겠 습 니 다. 당신 이 그 를 도와 줄 수 있 습 니까? 라 고 말 했다.
부품 을 들 기만 하면 내 려 놓 을 수 없 기 때문에 a 시 에 들 수 없다. b 시 에 내 려 놓 고 다른 부품 을 찾 으 러 가자.기본 스님 은 1 초 에 한 단위 의 거 리 를 걷 고 상하 좌우 네 방향 으로 만 갈 수 있 습 니 다. 만약 에 스님 이 지금 포신 을 들 고 있다 고 가정 하면 그 는 한 단위 의 거 리 를 걸 을 때마다 (t1 + 1) 초 가 필요 합 니 다. 만약 에 바퀴 를 들 면 그 는 지금 한 걸음 걸 을 때마다 (t1 + t2 + 1) 초 의 시간 이 필요 합 니 다. 이런 식 으로 유추 합 니 다.점 은 반복 해서 지나 갈 수 있 고 부품 이 있 는 점 을 지나 갈 때 가 져 가 거나 안 가 져 가 는 것 을 선택 할 수 있 습 니 다.
입력 설명:

         n, m      ，(1<=n, m <= 100)；   n    m  ‘#’ ‘.’     ，’#’   ，’.’   ，     ，          (     )，                  。      ，      10   sx,sy,x1, y1, x2, y2, x3, y3, ex, ed（   100）     ，      ，     ，     ，     ，      (  )，        。        t1, t2, t3，（     1，  100），      ，  ，              。        。

출력 설명:

         ，                。      。

예시 1
입력
 

3 5
##.##
.#.#.
##.##
1 3 2 1 2 3 2 5 3 3 
1 5 4

출력
 

34

설명 하 다.

       ，       2                         ，      ：   ->1    –> 3   -> 2   ->   
   (1,3),(2,3),(2,2),(2,1),(2,2),(2,3),(2,4),(2,5),(2,4),(2,3),(3,3)。
   34。

제목: 세 개의 부품 이 있 고, 각 부품 은 각자 의 무게 가 있 으 며, 하 나 를 가지 고 있 지 않 을 때 한 단 위 를 가 는 데 한 단위 의 시간 이 걸 리 며, 부품 을 담 은 후 걸 리 는 시간 에 이 부품 의 무 게 를 더 해 야 하 며, 세 개의 부품 을 모두 몸 에 담 을 때 는 안 되 며, 가장 짧 은 목표 에 도달 하 는 시간 을 출력 해 야 한다.
사고방식: 부품 이 비교적 적기 때문에 나 는 매 거 + BFS 를 이용 하여 부품 1, 부품 2, 부품 3 사 이 를 모두 배열 하여 표시 하 는데 6 개의 상황 만 있 고 그 다음 에 처음부터 끝까지 의 거 리 를 더 하면 OK 이다
AC 코드:

#include
using namespace std;
const int maxn = 1e2 + 5;
const int INF = 0x3f3f3f3f;

struct node
{
    int x, y, step;
};
char p[maxn][maxn];
int n, m, x1, yy, x2, y2, x3, y3;
int sx, sy, ex, ey, t1, t2, t3;
int s1, s2, s3, s4, min_ = INF;
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
bool vis[maxn][maxn];
bool check (int x, int y, int v) {
    if (v != t1 + t2 + t3) {  
        if (x > 0 && y > 0 && x <= n && y <= m && !vis[x][y]) return true;
        else return false;
    }
    else {  //           
        if (x > 0 && y > 0 && x <= n && y <= m && !vis[x][y] && p[x][y] != '#') return true;
        else return false;
    }
}
int bfs(int x, int y, int px, int py, int val) {   //val             
    queue  q;
    q.push({x, y, 0});
    memset(vis, 0, sizeof(vis));
    while (!q.empty()) {
        node now = q.front();
        q.pop();
        if (now.x == px && now.y == py) return now.step;
        for (int i = 0; i < 4; i++) {
            int xx = now.x + dir[i][0];
            int yy = now.y + dir[i][1];
            if (check (xx, yy, val)) {
                vis[xx][yy] = 1;
                q.push({xx, yy, now.step + val + 1});
            }
        }
    }
    return INF;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        getchar();
        for (int j = 1; j <= m; j++) scanf("%c", &p[i][j]);
    }
    cin >> sx >> sy >> x1 >> yy >> x2 >> y2 >> x3 >> y3 >> ex >> ey;
    cin >> t1 >> t2 >> t3;
    s1 = bfs(sx, sy, x1, yy, 0);
    s2 = bfs(x1, yy, x2, y2, t1);
    s3 = bfs(x2, y2, x3, y3, t1 + t2);
    s4 = bfs(x3, y3, ex, ey, t1 + t2 + t3);  //         ，          。。
    if (s1 != INF && s2 != INF && s3 != INF && s4 != INF) min_ = min (min_, s1 + s2 + s3 + s4);
    s2 = bfs(x1, yy, x3, y3, t1);
    s3 = bfs(x3, y3, x2, y2, t1 + t3);
    s4 = bfs(x2, y2, ex, ey, t1 + t2 + t3);
    if (s1 != INF && s2 != INF && s3 != INF && s4 != INF) min_ = min (min_, s1 + s2 + s3 + s4);
    s1 = bfs(sx, sy, x2, y2, 0);
    s2 = bfs(x2, y2, x1, yy, t2);
    s3 = bfs(x1, yy, x3, y3, t2 + t1);
    s4 = bfs(x3, y3, ex, ey, t1 + t2 + t3);
    if (s1 != INF && s2 != INF && s3 != INF && s4 != INF) min_ = min (min_, s1 + s2 + s3 + s4);
    s2 = bfs(x2, y2, x3, y3, t2);
    s3 = bfs(x3, y3, x1, yy, t2 + t3);
    s4 = bfs(x1, yy, ex, ey, t1 + t2 + t3);
    if (s1 != INF && s2 != INF && s3 != INF && s4 != INF) min_ = min (min_, s1 + s2 + s3 + s4);
    s1 = bfs(sx, sy, x3, y3, 0);
    s2 = bfs(x3, y3, x1, yy, t3);
    s3 = bfs(x1, yy, x2, y2, t1 + t3);
    s4 = bfs(x2, y2, ex, ey, t1 + t2 + t3);
    if (s1 != INF && s2 != INF && s3 != INF && s4 != INF) min_ = min (min_, s1 + s2 + s3 + s4);
    s2 = bfs(x3, y3, x2, y2, t3);
    s3 = bfs(x2, y2, x1, yy, t3 + t2);
    s4 = bfs(x1, yy, ex, ey, t1 + t2 + t3);
    if (s1 != INF && s2 != INF && s3 != INF && s4 != INF) min_ = min (min_, s1 + s2 + s3 + s4);
    cout << min_ << endl;
    return 0;
}

 
H. - 노자 의 전열 이 네요.
 
제목 설명
이 씨 는 스님 이 자신의 술 을 이 긴 것 을 보 았 지만 자신 이 아까워 서 뻔뻔 하 게 놀 았 다. 스님 에 게 '광 무 는 안 돼. 문 좀 더 해 줘. 1 - 8 의 순 서 를 다 말 해 주면 내 가 마 시 게 해 줄 게. 이번 에는 절대로 너 를 놀 리 지 않 을 거 야. 너 는 스님 을 도와 줄 수 있 니?' 라 고 말 했다.
입력 설명:

출력 설명:

1~8    ，          ，       。

예시 1
입력
 

No_Input

출력
 

Full arrangement of 1~8

비고:

1~3      ：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

AC 코드:

#include
using namespace std;

int p[10] = {1, 2, 3, 4, 5, 6, 7, 8};

int main()
{
    do {
        for (int i = 0; i < 7; i++) cout << p[i] << " ";
        cout << p[7] << endl;
    }
    while (next_permutation (p, p + 8));
    return 0;
}