原题链接

题目描述

​ 给定两点 $(x_1,y_1),(x_2,y_2)$，规定不超过 $t$ 步求从第一个点到第二个点的路径条数。

思路

​ 看上去就能搜，问题是超时是无法避免的，重点在于考虑如何优化。

​ 这里提供一个看似无关紧要但卡常很实用的范围判断优化。对于判断 $x \in [l,r]$，一种常规写法是 l<=x&&x<=r，实际上有更快的写法是 (x-l)|(r-x)>=0，具体原理可以参考韦易笑的知乎回答、回答2。

​ 但是，即便是加上这个优化，也仅仅从 40 到了 50，并没有满足我们的要求。

​ 考虑一个可行性剪枝，也就是考虑当前剩余步数不足以到达终点时，直接跳出，也就可以AC了

代码

#include <bits/stdc++.h>
using namespace std;
const int dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 };
int n, m, t, sa, sb, ea, eb, ans;
char ch;
bool okk[105][105];

void dfs(int x, int y, int cur) {
    if (x == ea && y == eb && cur == 0)
        ans++;
    if (!cur || abs(ea - x) + abs(eb - y) > cur)
        return;
    for (int i = 0; i < 4; i++) {
        int xx = dx[i] + x, yy = dy[i] + y;
        if (okk[xx][yy])
            dfs(xx, yy, cur - 1);
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> t;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> ch;
            if (ch == '.' && ((i - 1) | (n - i) | (j - 1) | (m - j)) >= 0)
                okk[i][j] = 1;
        }
    cin >> sa >> sb >> ea >> eb;
    dfs(sa, sb, t);
    cout << ans;
    return 0;
}