알고리즘 경연 입문 고전 (2 판) - 유 여가 - 제7 장 폭력 구 해법 연습 문제 (2 / 18)

16417 단어 알고리즘ACMuva알고리즘 경기 입문 고전
설명 하 다.
본 고 는 제 가 제7 장 18 개의 연습 문제 에 대한 정리 로 자서 인 에 맞 춰 본 고 를 읽 는 것 을 권장 합 니 다.그리고 문 제 를 쉽게 풀 수 있 도록 저 는 VOJ 에서 contest 를 열 었 습 니 다. 같이 하 는 것 을 환영 합 니 다. 제7 장 연습 문제 contest 는 어떤 문 제 를 직접 보고 싶 으 면 목록 을 클릭 하고 해당 하 는 문 제 를 푸 세 요!!
연습 문제
시 7 - 1 UVA 208 소방차
제목 은 n (n ≤ 20) 개의 결점 의 무방 향도 와 특정한 노드 k 를 입력 하고 사전 순서에 따라 작은 순서 에서 큰 순서 로 노드 1 에서 노드 k 까지 의 모든 경 로 를 출력 하 며 결점 이 중복 되 지 않도록 요구한다.사고 이 문 제 는 노드 1 이 노드 k 에 도착 할 수 있 는 지 를 미리 판단 해 야 한다. 그렇지 않 으 면 시간 을 초과 할 것 이다.DFS 가 옮 겨 다 니 거나 집 을 찾 는 등 여러 가지 방법 이 있다.그리고 DFS 를 옮 겨 다 니 면 되 지만 알고리즘 효율 을 고려 하여 역 추적 + 가지치기 방안 을 취 할 수 있 습 니 다.
나의 이 문 제 는 노드 1 이 노드 k 에 도달 할 수 있 는 지 를 판단 하 는 데 오래 걸 렸 다.내 코드 주 함수 중 여섯 번 째 줄 은 원래:
n = 0;
나중에 한참 을 조사해 보 니 바 뀌 었 다.
n = k;
AC 가 돼 요.원래 의 알고리즘 논리 에 따 르 면 n = 0 의 경우 주어진 데이터 에 이런 상황 이 발생 할 수 있 습 니 다.
제 시 된 모든 경로 에 나타 난 노드 가 k 보다 작 으 면 n 은 k 보다 작 습 니 다.
이때 노드 1 은 노드 k 에 도달 하지 못 할 것 이 고 첫 번 째 판단 은 정 답 을 줄 수 있 을 것 이다.하지만 결 과 는 내 가 고치 지 않 으 면 WA, 고치 면 AC.나 는 현재 알고리즘 논리 적 으로 여전히 이해 하지 못 하고 있다.만약 어떤 큰 신 이 알 고 있다 면, 아 낌 없 이 지적 해 주 십시오.
또한 이 문 제 는 가 지 를 자 를 수 있 고 시간 복잡 도 에 있어 중대 한 최적화 가 있 을 수 있 으 니 다른 블 로 그 를 참고 하 시기 바 랍 니 다.
코드
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

const int N = 21;

int n, k;
vector<int> neigh[N];
int v[N];
int path_count;
vector<int> path;

bool dfs(int u)
{
    if (u == k) return true;

    for (int i = 0; i < neigh[u].size(); i++) {
        if (!v[neigh[u][i]]) {
            int x = neigh[u][i];
            v[x] = 1;
            if (dfs(x)) return true;
        }
    }
    return false;
}

void find_path()
{
    path_count++;
    for (int i = 0; i < path.size(); i++)
        printf("%d%c", path[i], i == path.size()-1 ? '
' : ' ');
}

void search(int u)
{
    if (u == k) { find_path(); return; }

    for (int i = 0; i < neigh[u].size(); i++) {
        if (!v[neigh[u][i]]) {
            int x = neigh[u][i];
            v[x] = 1;
            path.push_back(x);
            search(x);
            path.resize(path.size()-1);
            v[x] = 0;
        }
    }
}

int main()
{
    int kase = 0;
    while (scanf("%d", &k) != EOF) {
        int a, b;
        int G[N][N];
        memset(G, 0, sizeof(G));
        n = k;
        while (scanf("%d%d", &a, &b), a || b) {
            n = max(n, max(a, b));
            G[a][b] = G[b][a] = 1;
        }
        for (int i = 1; i <= n; i++) {
            neigh[i].clear();
            for (int j = 1; j <= n; j++) {
                if (G[i][j]) neigh[i].push_back(j);
            }
        }

        printf("CASE %d:
", ++kase);
        memset(v, 0, sizeof(v));
        v[1] = 1;
        path_count = 0;
        if (dfs(1)) {
            path.clear();
            memset(v, 0, sizeof(v));
            v[1] = 1;
            path.push_back(1);
            search(1);
        }
        printf("There are %d routes from the firestation to streetcorner %d.
", path_count, k);
    }       

    return 0;
}

시 7 - 2 UVA 225 황금 도형
제목 의 평면 에 k 개의 장애 점 이 있다.(0, 0) 시 에서 출발 하여 첫 번 째 로 1 개 단 위 를 걷 고 두 번 째 로 2 개 단 위 를 걷는다.요 구 는 동서남북 방향 만 따라 갈 수 있 고 매번 90 ° 를 돌아 야 한다 (같은 방향 을 따라 계속 갈 수도 없고 뒤로 물 러 설 수도 없다).나 온 도형 은 자 교 할 수 있 지만 장애 점 을 지나 서 는 안 된다.사고방식 은 먼저 이 문제 의 번역 에 문제 가 있 고 매우 중요 한 판단 조건 을 빠 뜨 렸 다. 모든 착안점 은 이전 과 같 을 수 없다 (출발 할 때의 원점 은 계산 하지 않 는 다).그리고 나 서 나 는 모 르 는 사이 에 각종 WA 를나중에 다른 블 로 그 를 참고 해서 통 과 했 습 니 다.
그리고 이 문 제 는 조건 제약 이 좋 지 않다 고 생각 합 니 다. 각 도시 의 좌표 범 위 를 분명히 말 하고 기본 적 인 제약 을 해 야 합 니 다. 예 를 들 어 좌표 범 위 는 - 100 에서 100 사이 입 니 다.나 는 나중에 다른 블 로그 가 정의 한 좌표 범 위 를 참고 했다.그러나 좌표 범 위 를 주지 않 으 면 이 문제 도 풀 수 있 고 두 set 로 고장 점 과 착지 점 을 각각 저장 하여 무 게 를 판단 하면 된다.저 는 set 를 사용 하기 시 작 했 습 니 다. 제목 이 불분명 해서 제출 한 후에 WA 가 바 뀌 어서 지금의 코드 가 되 었 습 니 다.코드
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;

const char tow[] = "ensw";
const int dir[4][2] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};

typedef pair<int, int> P;

int n, k;
int G[250][250];
const int OFF = 105;
set<P> block;
int path_count;
vector<int> path;

void found_path()
{
    for (int i = 0; i < path.size(); i++)
      printf("%c", tow[path[i]]);
    printf("
");
    path_count++;
}

void dfs(P p)
{
    if (path.size() == n) {
        if (p == P(0, 0))
          found_path();
        return;
    }

    int m = path.size();
    for (int i = 0; i < 4; i++) {
        if (m && (path[m-1]+1)%4/2 == (i+1)%4/2) continue;
        P p1 = p;
        bool flag = true;
        for (int j = 1; j <= m+1; j++) {
            p1.first += dir[i][0];
            p1.second += dir[i][1];
            int x = p1.first, y = p1.second;
            if (abs(x) > OFF || abs(y) > OFF || G[p1.first+OFF][p1.second+OFF] == -1) {flag = false; break;}
        }
        if (flag && G[p1.first+OFF][p1.second+OFF] != 1) {
            path.push_back(i);
            G[p1.first+OFF][p1.second+OFF] = 1;
            dfs(p1);
            G[p1.first+OFF][p1.second+OFF] = 0;
            path.resize(m);
        }
    }
}

int main()
{
    int kase;
    scanf("%d", &kase);
    for (int t = 1; t <= kase; t++) {
        scanf("%d%d", &n, &k);
        int x, y;
        memset(G, 0, sizeof(G));
        for (int i = 0; i < k; i++) {
            scanf("%d%d", &x, &y);
            G[x+OFF][y+OFF] = -1;
        }

        path_count = 0;
        path.clear();
        dfs(P(0, 0));
        printf("Found %d golygon(s).

", path_count);
    }

    return 0;
}

시 7 - 3 UVA 211 도미 노 효과
제목
사고의 방향
코드

7-4 UVA 818

7-5 UVA 690

7-6 UVA 12113

7-7 UVA 12558

7-8 UVA 12107

7-9 UVA 1604

7-10 UVA 11214

7-11 UVA 12569 （ ）

7-12 UVA 1533

7-13 UVA 817

7-14 UVA 307

7-15 UVA 11882

7-16 UVA 11846

7-17 UVA 11694 Gokigen Naname

7-18 UVA 10384

Alfred에서 Inkdrop 문서 검색 허용
루비로 트위터 로봇 구축

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage