Home » 国际竞赛 » Details

USACO 2021 December Contest, Bronze Problem 3. Walking Home

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午2:50

USACO 2021 December Contest, Bronze Problem 3. Walking Home

Bessie the cow is trying to walk from her favorite pasture back to her barn.

The pasture and farm are on an $N \times N$ grid ( $2 \leq N \leq 50$ ), with her pasture in the top-left corner and the barn in the bottom-right corner. Bessie wants to get home as soon as possible, so she will only walk down and to the right. There are haybales in some locations that Bessie cannot walk through; she must walk around them.

Bessie is feeling a little tired today, so she wants to change the direction she walks at most $K$ times ( $1 \leq K \leq 3$ ) .

How many distinct paths can Bessie walk from her favorite pasture to the barn? Two paths are distinct if Bessie walks in a square in one path but not in the other.

INPUT FORMAT (input arrives from the terminal / stdin):

The input for each test case contains $T$ sub-test cases, each describing a different farm and each of which must be answered correctly to pass the full test case. The first line of input contains $T$ ( $1 \leq T \leq 50$ ). Each of the $T$ sub-test cases follow.Each sub-test case starts with a line containing $N$ and $K$ .

The next $N$ lines each contain a string of $N$ characters. Each character is either $.$ if it is empty or $H$ if it has a haybale. It is guaranteed the top-left and bottom-right corners of the farm will not contain haybales.

OUTPUT FORMAT (print output to the terminal / stdout):

Output $T$ lines, the $i$ th line containing the number of distinct paths Bessie can take in the $i$ th sub-test case.

SAMPLE INPUT:

7
3 1
...
...
...
3 2
...
...
...
3 3
...
...
...
3 3
...
.H.
...
3 2
.HH
HHH
HH.
3 3
.H.
H..
...
4 3
...H
.H..
....
H...

SAMPLE OUTPUT:

We'll denote Bessie's possible paths as strings of D's and R's, indicating that Bessie moved either down or right, respectively.

In the first sub-test case, Bessie's two possible walks are DDRR and RRDD.

In the second sub-test case, Bessie's four possible walks are DDRR, DRRD, RDDR, and RRDD.

In the third sub-test case, Bessie's six possible walks are DDRR, DRDR, DRRD, RDDR, RDRD, and RRDD.

In the fourth sub-test case, Bessie's two possible walks are DDRR and RRDD.

In the fifth and sixth sub-test cases, it is impossible for Bessie to walk back to the barn.

In the seventh sub-test case, Bessie's six possible walks are DDRDRR, DDRRDR, DDRRRD, RRDDDR, RRDDRD, and RRDRDD.

SCORING:

Test case 2 satisfies $K = 1$ .
Test cases 3-5 satisfy $K = 2$ .
Test cases 6-10 satisfy $K = 3$ .

Problem credits: Nick Wu

USACO 2021 December Contest, Bronze Problem 3. Walking Home 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Nick Wu)

The subtasks in this problem motivate starting by solving the problem when $K = 1$ and then going from there to solving the problem when $K = 2$ and then $K = 3$ . As a result, this editorial will go through solving each of these in order.

$K = 1$ : If Bessie can only turn once, she must turn at either the top-right corner or the bottom-left corner. Therefore, it suffices to check that the top row and right column are empty and that the bottom row and left column are empty.

$K = 2$ : If Bessie is to make exactly two turns, then either she walks along the top row, turns right and walks all the way to the bottom and then turns left, or she walks along the left column, turns left, and walks all the way to the right and then turns right. In the former case, we can brute force all columns Bessie would select. In the latter case, we can brute force all rows Bessie would select.

$K = 3$ : If Bessie is to make exactly three turns, then Bessie ends up turning in the middle of the grid in some square that is not in the top row, bottom row, left column, or right column. We can brute force all inner squares that Bessie would select.

The runtime for a single test case is $O (N^{3})$ - there are $O (N^{2})$ paths that Bessie can consider, and there are $O (N)$ squares on each path to validate as being empty.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

void solve() {
  int n, k;
  cin >> n >> k;
  vector<string> g(n);
  for(int i = 0; i < n; i++) cin >> g[i];
  int ret = 0;
  if(k >= 1) {
    bool urcorner = true;
    bool dlcorner = true;
    for(int i = 0; i < n; i++) {
      if(g[0][i] == 'H' || g[i][n-1] == 'H') urcorner = false;
      if(g[i][0] == 'H' || g[n-1][i] == 'H') dlcorner = false;
    }
    ret += urcorner;
    ret += dlcorner;
  }
  if(k >= 2) {
    // use column j
    for(int j = 1; j < n-1; j++) {
      bool valid = true;
      for(int i = 0; i < n; i++) {
        if(g[i][j] == 'H') valid = false;
        if(i < j && g[0][i] == 'H') valid = false;
        if(i > j && g[n-1][i] == 'H') valid = false;
      }
      ret += valid;
    }
    // use row i
    for(int i = 1; i < n-1; i++) {
      bool valid = true;
      for(int j = 0; j < n; j++) {
        if(g[i][j] == 'H') valid = false;
        if(j < i && g[j][0] == 'H') valid = false;
        if(j > i && g[j][n-1] == 'H') valid = false;
      }
      ret += valid;
    }
  }
  if(k >= 3) {
    for(int i = 1; i < n-1; i++) {
      for(int j = 1; j < n-1; j++) {
        // RDRD
        bool valid = g[i][j] == '.';
        for(int a = 0; a < n; a++) {
          if(a <= i && g[a][j] == 'H') valid = false;
          if(a >= i && g[a][n-1] == 'H') valid = false;
          if(a <= j && g[0][a] == 'H') valid = false;
          if(a >= j && g[i][a] == 'H') valid = false;
        }
        ret += valid;
        valid = g[i][j] == '.';
        // DRDR
        for(int a = 0; a < n; a++) {
          if(a <= i && g[a][0] == 'H') valid = false;
          if(a >= i && g[a][j] == 'H') valid = false;
          if(a <= j && g[i][a] == 'H') valid = false;
          if(a >= j && g[n-1][a] == 'H') valid = false;
        }
        ret += valid;
      }
    }
  }
  cout << ret << "\n";
}
int main() {
  int t;
  cin >> t;
  while(t--) solve();
}

We can also solve this problem in $O (N^{2} K)$ time by storing for each square, each possible number of turns (up to $K$ ), and each of the directions D and R, the number of ways for Bessie to reach that square using exactly that number of turns such that the last direction in which she walked was that direction. However, this is outside of the scope of both Bronze and Silver.

[/hide]