USACO 2014 December Contest, Bronze Problem 2. Crosswords

Category: 计算机国际竞赛 Date: 2017年12月5日上午11:08

原题下载

USACO2014DEC-B2

答案

(Analysis by Jonathan Paulson - jonathanpaulson@gmail.com)

We can go along the squares in top-to-bottom, left-to-right order. For each square, we want to see if it starts a clue. It can start either a horizontal or vertical clue. For it to start a horizontal clue, the cell to the left must be blocked or off the board, and the two cells to the right must be clear and on the board. Similarly, to start a vertical clue, the cell above must be blocked or off the board, and the two cells below must be on the board and clear.

As we find cells that start a clue, we can add them to a list. Then at the end, we need to print the size of the list and its contents. Here's my C++ code:

#include <cstdio>
#include <vector>

#define MP make_pair
#define PB push_back
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

int main() {
  ll R, C;
  scanf("%lld %lld\n", &R, &C);
  vector<vector<char> > G(R, vector<char>(C, ' '));
  for(ll r=0; r<R; r++) {
    char buf[100];
    scanf("%s", buf);
    for(ll c=0; c<C; c++) {
      G[r][c] = buf[c];
    }
  }
  vector<pll> A;

  for(ll r=0; r<R; r++) {
    for(ll c=0; c<C; c++) {
      bool horizontal = (c+2<C && G[r][c]=='.' && G[r][c+1]=='.' && G[r][c+2]=='.' &&
                         (c==0 || G[r][c-1]=='#'));
      bool vertical = (r+2<R && G[r][c]=='.' && G[r+1][c]=='.' && G[r+2][c]=='.' &&
                       (r==0 || G[r-1][c]=='#'));
      if(horizontal || vertical) {
        A.PB(MP(r+1, c+1));
      }
    }
  }
  printf("%lu\n", A.size());
  for(pll clue : A) {
    printf("%lld %lld\n", clue.X, clue.Y);
  }
}

以上就是关于【USACO 2014 December Contest, Bronze Problem 2. Crosswords】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

美国AI奥赛首次新增低龄组！2027 USAAIO报名中，2月正式开考！

不考编程实操？2026 CAICP人工智能能力认证首轮11月22日开考，备考指南速递！