【第16题】题解及代码分享：没记忆化搜索A了，[USACO21DEC] Walking Home B

2023-11-28 17:09:54 浏览数 (1)

大家好，我是小码匠，今天继续划水，在记忆化搜索那块弄了半天，没搞定，后来给去掉了，结果AC了，惊喜。。。

前置知识

  • 搜索

路漫漫其修远兮，吾将上下而求索

离自己的既定目标：

  • 目标：300道
  • 已完成：16道
  • 待完成：284道

题目描述

题目地址：

  • 洛谷：https://www.luogu.com.cn/problem/P7995

奶牛 Bessie 正准备从她最喜爱的草地回到她的牛棚。

农场位于一个 N×N 的方阵上（2≤N≤50），其中她的草地在左上角，牛棚在右下角。Bessie 想要尽快回家，所以她只会向下或向右走。有些地方有草堆（haybale），Bessie 无法穿过；她必须绕过它们。

Bessie 今天感到有些疲倦，所以她希望改变她的行走方向至多 K 次（1≤K≤3）。

Bessie 有多少条不同的从她最爱的草地回到牛棚的路线？如果一条路线中 Bessie 经过了某个方格而另一条路线中没有，则认为这两条路线不同。

输入格式

每个测试用例的输入包含 T 个子测试用例，每个子测试用例描述了一个不同的农场，并且必须全部回答正确才能通过整个测试用例。输入的第一行包含 T（1≤T≤50）。每一个子测试用例如下。

每个子测试用例的第一行包含 N 和 K。

以下 N 行每行包含一个长为 N 的字符串。每个字符为 ..，如果这一格是空的，或 H，如果这一格中有草堆。输入保证农场的左上角和右下角没有草堆。

输出格式

输出 T 行，第 i 行包含在第 i 个子测试用例中 Bessie 可以选择的不同的路线数量。

输入输出样例

输入 #1复制

代码语言：javascript复制
7
3 1
...
...
...
3 2
...
...
...
3 3
...
...
...
3 3
...
.H.
...
3 2
.HH
HHH
HH.
3 3
.H.
H..
...
4 3
...H
.H..
....
H...

输出 #1复制

代码语言：javascript复制
2
4
6
2
0
0
6
说明/提示

【样例解释】

我们将使用一个由字符 D 和 R 组成的字符串来表示 Bessie 的路线，其中 D 和 R 分别表示 Bessie 向下（down）或向右（right）移动。

第一个子测试用例中，Bessie 的两条可能的路线为 DDRR 和 RRDD。

第二个子测试用例中，Bessie 的四条可能的路线为 DDRR，DRRD，RDDR 和 RRDD。

第三个子测试用例中，Bessie 的六条可能的路线为 DDRR，DRDR，DRRD，RDDR，RDRD 和 RRDD。

第四个子测试用例中，Bessie 的两条可能的路线为 DDRR 和 RRDD。

第五和第六个子测试用例中，Bessie 不可能回到牛棚。

第七个子测试用例中，Bessie 的六条可能的路线为 DDRDRR，DDRRDR，DDRRRD，RRDDDR，RRDDRD 和 RRDRDD。

【数据范围】

  • 测试点 2 满足 K=1。
  • 测试点 3-5 满足 K=2。
  • 测试点 6-10 满足 K=3。

题解

  • https://www.luogu.com.cn/problem/solution/P7995
AC代码
代码语言：javascript复制
// 题目: P7995 [USACO21DEC] Walking Home B
// 链接: https://www.luogu.com.cn/problem/P7995
// 难度: 普及/提高−
// 题解:
// - 洛谷: https://www.luogu.com.cn/problem/solution/P7995
// - USACO:
#include <bits/stdc  .h>

using namespace std;
int n, k;
int g[1000][10000];
string s[1000];

int dfs(int x, int y, int t, int w) {
    if (t > k || s[x][y] == 'H' || x > n || y > n) {
        return 0;
    }

    if (x == n && y == n) {
        return 1;
    }

//    if (g[x][y] != 0) {
//        return g[x][y];
//    }

    int sum = 0;
    if (w == 0) {
        sum  = dfs(x   1, y, t   1, 1);
        sum  = dfs(x, y   1, t, 0);
    } else {
        sum  = dfs(x   1, y, t, 1);
        sum  = dfs(x, y   1, t   1, 0);
    }

    return sum;
}

void best_coder() {
    int q;
    cin >> q;

    while (q--) {
        cin >> n >> k;
        --n;
        for (int i = 0; i <= n;   i) {
            cin >> s[i];
        }
        memset(g, 0, sizeof(g));
        cout << dfs(0, 1, 0, 0)   dfs(1, 0, 0, 1) << 'n';
    }

}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}
学习代码
代码语言：javascript复制
#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();
}

END

int 数据 搜索 效率 字符串

0 人点赞