USACO 2014 December Contest, Bronze Problem 2. Crosswords

原题下载

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】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

5金3银！2026 IOAI国际人工智能奥赛收官！中国队取得历史性突破！

AI奥赛2026国家队名单公布！ 新赛季翰林助力直通IOAI全球总决赛！