結果

問題 No.2928 Gridpath
ユーザー erbowl
提出日時 2024-10-12 16:20:05
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 1,358 bytes
コンパイル時間 2,809 ms
コンパイル使用メモリ 258,672 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-12 16:20:18
合計ジャッジ時間 3,577 ms
ジャッジサーバーID
（参考情報） 		judge / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

typedef long long ll;
typedef long double ld;

#include <bits/stdc++.h>
using namespace std;
const ll MOD = 998244353;
signed main() {
    ll h,w;
    std::cin >> h>>w;
    ll si,sj,gi,gj;
    std::cin >> si>>sj>>gi>>gj;
    si--;sj--;gi--;gj--;
    vector<vector<ll>> edges(h*w);
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if(i+1<h){
                edges[j+w*i].push_back(j+w*(i+1));
                edges[j+w*(i+1)].push_back(j+w*i);
            }
            if(j+1<w){
                edges[j+w*i].push_back(j+1+w*i);
                edges[j+1+w*i].push_back(j+w*i);
            }
        }
    }
    ll ans = 0;
    set<ll> visit;
    visit.insert(sj+si*w);
    function<void(ll)> dfs = [&](ll now){
        if(now==gj+gi*w){
            ans++;
            return;
        }
        for (auto e : edges[now]) {
            if(visit.find(e)!=visit.end())continue;
            bool ok = true;
            for (auto ee : edges[e]) {
                if(ee==now)continue;
                if(visit.find(ee)!=visit.end()){
                    ok=false;
                    break;
                }
            }
            if(ok){
                visit.insert(e);
                dfs(e);
                visit.erase(e);
            }
        }
    };
    
    dfs(sj+si*w);
    
    std::cout << ans << std::endl;
};
0