Как решить USACO 2013-Периметр-Серебро Рекурсивно - PullRequest
Новая
       18

Как решить USACO 2013-Периметр-Серебро Рекурсивно

0 голосов
/ 23 января 2020

Итак, я решал этот серебряный конкурс USACO 2013 - Периметр - Задача 1.

Ссылка на проблему: Ссылка на проблему

Ссылка на бронзовую версию эта проблема: Проблема Ссылка

Ссылка на решения: Серебро - Ссылка на решение Бронза - Ссылка на решение

Задача:

Задача 1: Периметр [Брайан Дин, 2013]

Фермер Джон устроил N тюков сена (1 <= N <= 50 000) в середине одно из его полей. Если мы рассматриваем поле как сетку 1 000 000 x 1 000 000 из 1 x 1 квадратных ячеек, каждый тюк сена занимает ровно одну из этих ячеек (конечно, нет двух тюков сена, занимающих одну и ту же ячейку). </p>

FJ что все его тюки сена образуют одну большую связную область, а это означает, что начиная с любого тюка, можно достичь любого другого тюка, совершив серию шагов на север, юг, восток или запад, на непосредственно смежные тюки. Однако связанная область тюков сена может содержать «дыры» - пустые области, которые полностью окружены тюками сена.

Пожалуйста, помогите FJ определить периметр области, образованной его тюками сена. Обратите внимание, что отверстия не влияют на периметр.

ИМЯ ПРОБЛЕМЫ: периметр

ФОРМАТ ВХОДА:

  • Строка 1: Количество тюков сена, N.

  • Строки 2..1 + N: Каждая строка содержит местоположение (x, y) одного тюка сена, где x и y - целые числа в диапазоне 1. .1,000,000. Позиция (1,1) - это левая нижняя ячейка в поле FJ, а позиция (1000000,1000000) - это правая верхняя ячейка.

SAMPLE INPUT (файл perimeter.in) :

8

10005 200003

10005 200004

10008 200004

10005 200005

10006 200003

10007 200003

10007 200004

10006 200005

ВХОДНЫЕ ДАННЫЕ:

Связанная область, состоящая из тюков сена, выглядит следующим образом:

XX

X XX

XXX

ФОРМАТ ВЫХОДА:

  • Линия 1: Периметр подключенной области тюков сена .

ВЫБОР ВЫБОРКИ (файл perimeter.out):

14

ДЕТАЛИ ВЫХОДА:

Длина периметра подключенной области равно 14 (например, левая сторона области дает длину 3 в эту сумму). Заметьте, что отверстие в середине не влияет на это число.

Что я сделал

Я продолжил рекурсивное решение проблемы, которое выглядит следующим образом: 

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

#define rep(i,a,b) for(auto (i)=a;i<b;i++)
#define list(i,N) for(auto (i)=0;i<N;i++)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
#define mp make_pair
#define pb push_back

#define int ll
#define INF 1e18+5
#define mod 1000000007
//One map for storing whether a cell has hay bale or not
//And the other for visited - whether a cell has been visited or not
map<pi,bool> vis;
map<pi,bool> exists;
int ans = 0;

void solve(int i, int j){
    //Check about the visited stuff
    if(vis[mp(i,j)]) return;
    vis[mp(i,j)] = true;
    //Find the answer now
    ans += 4;
    if(exists[mp(i-1,j)]){
        --ans; solve(i-1,j);    
    }
    if(exists[mp(i+1,j)]){
        --ans; solve(i+1,j);
    }
    if(exists[mp(i,j+1)]){
        --ans; solve(i,j+1);
    }
    if(exists[mp(i,j-1)]){
        --ans; solve(i,j-1);
    }
}

int32_t main(){

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int N; cin >> N;
    int first, second; //the starting point where we start the function...
    while(N--){
        int a,b; cin >> a >> b;
        first = a; second = b; //in the end, it is just the coordinate specified in the last in the input...
        exists[mp(a,b)] = true; //Hay Bale exists...
    }

    solve(first,second);
    cout << ans << "\n";

    return 0;
}

В основном я делаю следующее:

  1. Начало с ячейки.

  2. Сначала проверьте, камера была ранее посещена. Если да, вернись. Если нет, сделайте это посещением.

  3. Добавьте 4 к счетчику для всех четырех сторон.

  4. Осмотрите ячейку на всех соседних с ней клетки. Если в ячейке также есть сенажи, вычтите 1 из счетчика (не нужно добавлять границу), а затем перейдите к 2.

Проблема, с которой я сталкиваюсь

Обратите внимание, что этот код также считает границу, требуемую внутри отверстия. НО нам не нужно включать это в наш ответ. Я, однако, не знаю, как исключить это из нашего ответа ...

Почему я упомянул Бронзовую проблему

Если вы видите решение Бронзы Проблема (которая является той же самой проблемой, но с другими ограничениями), мистер Брайан Дин также реализует этот вид рекурсивного решения, которое похоже на то, что я делаю в своем коде. Код приведен ниже: 

#include <stdio.h>
#define MAX_N 100

int already_visited[MAX_N+2][MAX_N+2];
int occupied[MAX_N+2][MAX_N+2];
int perimeter;

int valid(int x, int y)
{
  return x>=0 && x<=MAX_N+1 && y>=0 && y<=MAX_N+1;
}

void visit(int x, int y)
{
  if (occupied[x][y]) { perimeter++; return; }
  if (already_visited[x][y]) return;
  already_visited[x][y] = 1;
  if (valid(x-1,y)) visit(x-1,y);
  if (valid(x+1,y)) visit(x+1,y);
  if (valid(x,y-1)) visit(x,y-1);
  if (valid(x,y+1)) visit(x,y+1);
}

int main(void)
{
  int N, i, x, y;

  freopen ("perimeter.in", "r", stdin);
  freopen ("perimeter.out", "w", stdout);

  scanf ("%d", &N);
  for (i=0; i<N; i++) {
    scanf ("%d %d", &x, &y);
    occupied[x][y] = 1;
  }

  visit(0,0);

  printf ("%d\n", perimeter);
  return 0;
}

Почему это решение не работает для Silver

Это связано с тем, что в Silver версии есть проблема, которую я У решения есть более высокие ограничения, но тот же срок. Это время ожидания кода.

Итак, я был бы признателен, если бы кто-нибудь мог помочь мне решить эту проблему, чтобы исключить периметр, занимаемый отверстием в середине.

1 Ответ

1 голос
/ 05 февраля 2020

Ваше решение очень похоже на второе опубликованное. Но вместо того, чтобы идти по тюкам, вы идете по периметру: 

void solve(int i, int j){
    if(vis[mp(i,j)]) return;
    if(exists[mp(i,j)]) return;
    if(there_is_no_bale_next_to(i,j)) return; // consider all 8 directions
    vis[mp(i,j)] = true;
    ans ++;
    solve(i-1,j);    
    solve(i+1,j);
    solve(i,j+1);
    solve(i,j-1);
}

Сначала вы запускаете solve в точке, определенной по периметру (например, в самой западной точке).

...