c++ - 如何递归解决 USACO 2013-Perimeter-Silver

问题描述

所以我正在解决这个 USACO 2013 年 2 月银牌比赛 - 周长 - 问题 1。

本题青铜版链接：Problem Link

问题：

问题 1：周界 [Brian Dean, 2013]

农夫约翰在他的一块田地中间安排了 N 个干草包（1 <= N <= 50,000）。如果我们将场视为 1,000,000 x 1,000,000 的 1 x 1 方形单元格，每个干草捆恰好占据这些单元格中的一个（当然，没有两个干草捆占据同一个单元格）。

FJ 注意到他的干草捆都形成了一个大的相连区域，这意味着从任何草捆开始，通过向北、南、东或西方向直接相邻的草捆采取一系列步骤，可以到达任何其他草捆。然而，干草捆的连接区域可能包含“洞”——完全被干草捆包围的空白区域。

请帮助 FJ 确定他的干草捆形成的区域的周长。请注意，孔不影响周长。

问题名称：周长

输入格式：

第 1 行：干草捆数，N。
第 2..1+N 行：每行包含一个干草捆的 (x,y) 位置，其中 x 和 y 都是 1..1,000,000 范围内的整数。位置 (1,1) 是 FJ 字段中左下角的单元格，位置 (1000000,1000000) 是右上角的单元格。

样本输入（文件 perimeter.in）：

10005 200003

10005 200004

10008 200004

10005 200005

10006 200003

10007 200003

10007 200004

10006 200005

输入细节：

由干草捆组成的连通区域如下所示：

X XX

XXX

输出格式：

第 1 行：干草捆相连区域的周长。

样本输出（文件 perimeter.out）：

输出细节：

连接区域的周长长度为 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;
}

基本上，我正在做的是：

从一个细胞开始。
首先，检查之前是否访问过该单元格。如果是，请返回。如果没有，请访问它。
将 4 添加到所有四个面的计数器。
环顾该单元格以查看其所有相邻单元格。如果单元格也有干草，请从计数器中减去 1（无需添加边界），然后转到 2。

我面临的问题

请注意，此代码还计算了孔内所需的边界。但是我们不需要将其包含在我们的答案中。但是，我不知道如何从我们的答案中排除它......

为什么我提到青铜问题

如果您看到青铜问题的解决方案（这只是相同的问题，但具有不同的约束），Brian Dean 先生也在这里实现了这种递归解决方案，这与我在代码中所做的类似。代码如下：

#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 版本中的约束具有更高的约束，但具有相同的时间限制。这会使代码超时。

所以，如果有人能帮我解决这个问题，以排除中间孔占据的周边，我将不胜感激。

标签： c++algorithmrecursionhashmapc++14

c++ - 如何递归解决 USACO 2013-Perimeter-Silver

问题描述

解决方案

推荐阅读