[ABC341C] Takahashi Gets Lost 的题解

· · 题解

[ABC341C] Takahashi Gets Lost 的题解

题目大意

给你一个图，. 表示可以通行，# 表示不可以通行，还给你一个操作指令串，U 代表向上走一格，D 代表向下走一格，L 代表向左走一格，R 代表向右走一格，问你有多少种起始点，按照指令走，可以不经过障碍走完，输出方案数。

思路

既然 1 \le W,H \le 500，考虑直接暴力。

枚举每一个起点 (i,j)，随后看看按照规定能否走完，如果可以，ans++，否则，去看下一个起点。

时间复杂度 O(WHN)。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, k;
string goes;
string str[505];
int ans;
int _turn[128][2];

bool check(int x, int y)
{
    int a = x, b = y;
    int i = 0;
    while (i < k && x >= 0 && y >= 0 && x < n && y < m && str[x][y] == '.')
        x += _turn[goes[i]][0], y += _turn[goes[i]][1], i++;
    if (str[x][y] != '.')
        return 0;
    return 1;
}

int main()
{
    _turn['L'][0] = 0, _turn['L'][1] = -1;
    _turn['R'][0] = 0, _turn['R'][1] = 1;
    _turn['U'][0] = -1, _turn['U'][1] = 0;
    _turn['D'][0] = 1, _turn['D'][1] = 0;
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m >> k;
    cin >> goes;
    for (int i = 0; i < n; i++)
        cin >> str[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            ans += check(i, j);
    cout << ans;
    return 0;
}