[CSES] Grid paths

Đề bài

Có tất cả 88148 đường đi trên bảng 7×7 từ ô trái trên của bảng đến ô trái dưới của bảng. Mỗi đường đi có chính xác 48 kí tự bao gồm các kí từ ${D(down),U(up),L(left),R(right)}$. Ví dụ:

Đường đi này tương ứng với miêu tả

Nhiệm vụ của bạn là đếm số lượng đường đi có thể có của một chỉ dẫn. Chỉ dẫn có thể có nhiều kí tự ? (bạn có thể đi đủ 4 hướng).

Dữ liệu:

• Một dòng chứa 48 kí tự bao gồm ${?,D,U,L,R}$.

Kết quả:

• In ra một số nguyên là tổng số đường đi thõa mãn.

Ví dụ:

Hướng dẫn

• Ở bài này nếu chúng ta chạy backtracking hết tất cả trường hợp thì sẽ độ phức tạp vì mỗi ô ta có 4 trường hợp nên sẽ là $O(4^{48})$ rất là lớn.
• Vì thế chúng ta sẽ tối ưu những cái nhỏ những cái nhỏ này sẽ làm độ phức tạp thuật toán giảm đi rất nhiều. Các trường hợp chúng ta có thể bỏ như sau
  • Nếu chúng ta vào một đường dẫn mà nó đụng lại đường đi thì chắc chẵn đó không thể tạo thành một đường đi hợp lệ và ta có thể bỏ qua trường hợp đó..

• Dù chỉ là một bước tối ưu rất nhỏ có khi chúng ta không để ý nhưng nó có thể biến lời giải có độ phức tạp lớn về rất nhỏ
• Kĩ thuật này gọi là “Pruning the search” và có rất nhiều cách tối ưu khác. Đây là cách dể cài và tối ưu nhất.

Mã nguồn tham khảo

#include <bits/stdc++.h>
using namespace std;
#define task "test"
const int N = 1e5+1;
typedef pair<int,int> pi;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
string s;
int vis[9][9];
int ans = 0;

void dfs(int i,int j,int step){

    if(i==7&&j==1) {
        ans+=(step==48);
        return;
    }
    if(i < 1 || i > 7 || j < 1 || j > 7 || vis[i][j]) return;
    if(!vis[i - 1][j] && !vis[i + 1][j] && vis[i][j + 1] && vis[i][j - 1]) return;
    if(vis[i - 1][j] && vis[i + 1][j] && !vis[i][j + 1] && !vis[i][j - 1]) return;
    // kiểm tra đường đi có quay lại đụng hay không
    // check cả cột và hàng

    vis[i][j]=1;
    if(s[step] == 'D' || s[step]=='?'){
        dfs(i + 1, j, step + 1);
    }
    if(s[step] == 'U' || s[step]=='?'){
        dfs(i - 1, j, step + 1);
    }
    if(s[step] == 'R' || s[step]=='?'){
        dfs(i, j + 1, step + 1);
    }
    if(s[step] == 'L' || s[step]=='?'){
        dfs(i, j - 1, step + 1);
    }
//    if(s[step] == '?'){
//        dfs(i + 1, j, step + 1);
//        dfs(i - 1, j, step + 1);
//        dfs(i, j + 1, step + 1);
//        dfs(i, j - 1, step + 1);
//    }

    vis[i][j]=0;
}
void solve(){


   cin >> s;
   // tạo viền để ta có thể kiểm tra xem đường đi của ta
   // có đụng tường không
   // trường hợp đụng tường là trường hợp đặc biệt.
   for(int i=1;i<=7;i++){
       vis[0][i]=1;
       vis[i][0]=1;
       vis[8][i]=1;
       vis[i][8]=1;
   }

   dfs(1,1,0);

   cout << ans;



}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    int t;
    t=1;
    while(t-->0){
        solve();
    }

}