CSES Grid Paths
// compile: g++ -o data data.cpp -std=gnu++20 -DLOCAL
// run: ./data < data.in
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#endif
#define sz(v) ((int)(v).size())
#define PV(v) for (int i=0;i<v.size();++i)cout<<v[i]<<" ";cout<<endl;
#define INTINF 9223372036854775807
#define int long long

using namespace std;

int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int n = 7;
int vis[9][9];
int s[100];
int cnt, total = 0;

bool ok(int x, int y) {
    return !vis[x][y];
}

bool iswall(int x, int y) {
    return !(x>=1 && y>=1 && x<=n && y<=n);
}

void dfs(int x, int y, int k) {
    if (x==n && y==1 && k>=n*n) {
        if (cnt == n*n) ++total;
        return;
    }
    if ((x==n-1 && y==0) || k>=n*n) return;
    // if (vis[x + dir[pre][0]][y + dir[pre][1]]) {
    //     int l = (pre - 1) % 4, r = (pre + 1) % 4;
    //     if (!vis[x + dir[l][0]][y + dir[l][1]] && !vis[x + dir[r][0]][y + dir[r][1]]) return;
    // }
    for (int i = 0; i < 4; ++i) {
        int l = (i - 1) % 4, r = (i + 1) % 4, oppo = (i + 2) % 4;
        if (vis[x + dir[i][0]][y + dir[i][1]] && vis[x + dir[oppo][0]][y + dir[oppo][1]] && !vis[x + dir[l][0]][y + dir[l][1]] && !vis[x + dir[r][0]][y + dir[r][1]]) return;
    }
    if (~s[k]) {
        int i = s[k];
        if (vis[x + dir[i][0]][y + dir[i][1]]) return;
        vis[x + dir[i][0]][y + dir[i][1]] = 1;
        ++cnt;
        dfs(x + dir[i][0], y + dir[i][1], k + 1);
        --cnt;
        vis[x + dir[i][0]][y + dir[i][1]] = 0;
        return;
    }
    int dx = -1, dy = -1, m = 0;
    for (int i = 0; i < 4; ++i) {
        int xx = x + dir[i][0], yy = y + dir[i][1];
        if (vis[xx][yy] || (xx == n && yy == 1)) continue;
        int total = 0;
        for (int j = 0; j < 4; ++j) total += vis[xx + dir[j][0]][yy + dir[j][1]];
        if (total == 3) {
            ++m;
            dx = xx;
            dy = yy;
        }
    }
    if (m > 1) return;
    if (m == 1) {
        vis[dx][dy] = 1;
        ++cnt;
        dfs(dx, dy, k + 1);
        --cnt;
        vis[dx][dy] = 0;
        return;
    }
    for (int i = 0; i < 4; ++i) {
        if (vis[x + dir[i][0]][y + dir[i][1]]) continue;
        vis[x + dir[i][0]][y + dir[i][1]] = 1;
        ++cnt;
        dfs(x + dir[i][0], y + dir[i][1], k + 1);
        --cnt;
        vis[x + dir[i][0]][y + dir[i][1]] = 0;
    }
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    for (int i = 1; i < n*n; ++i) {
        char ch; cin >> ch;
        if (ch == '?') s[i] = -1;
        else if (ch == 'R') s[i] = 0;
        else if (ch == 'D') s[i] = 1;
        else if (ch == 'L') s[i] = 2;
        else if (ch == 'U') s[i] = 3;
    }
    vis[1][1] = 1;
    for (int i = 0; i <= (n+1); ++i) {
        vis[0][i] = vis[i][0] = vis[n+1][i] = vis[i][n+1] = 1;
    }
    cnt = 1;
    dfs(1, 1, 1);
    cout << total << endl;

    return 0;
}

Comments

  1. 2 months ago
    2025-12-06 2:34:33

    Okay, so I downloaded stargameapk. Kinda cool if you’re on the go and want something to play on your phone. Not gonna lie, it’s pretty addictive. Check out stargameapk if you’re looking for some mobile gaming fun.

  2. 2 months ago
    2025-12-19 13:49:38

    Been using Zalopay to top up my Fun88 account thanks to the advice from fun88forum.com. Super convenient! Try it yourself at: nạp tiền fun88 zalopay

  3. 1 month ago
    2025-12-29 6:17:51

    Just ran across 79kinh. Seems promising! Worth a punt if you’re bored and looking for a chance to win!. Follow this link and good luck!: 79kinh

Send Comment Edit Comment


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
Previous
Next