結果

問題 No.2838 Diagonals
コンテスト
ユーザー pockyny
提出日時 2025-07-15 00:57:52
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 38 ms / 2,000 ms
コード長 3,403 bytes
コンパイル時間 5,614 ms
コンパイル使用メモリ 84,144 KB
実行使用メモリ 13,544 KB
最終ジャッジ日時 2025-07-15 10:14:36
合計ジャッジ時間 9,617 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>

using namespace std;
struct UF{
    vector<int> par,sz;
    vector<vector<int>> mergeTree;
    UF(int n, bool useMergeTree = false){
        sz.resize(n); par.resize(n);
        for(int i=0;i<n;i++) sz[i] = 1, par[i] = i;
        if(useMergeTree){
            sz.resize(2*n); par.resize(2*n);
            for(int i=n;i<2*n;i++) sz[i] = 1, par[i] = i;
            mergeTree.resize(2*n);
        }
    }
    int find(int x){
        if(par[x]==x) return x;
        return par[x] = find(par[x]); 
    }
    void unite(int x,int y){
        x = find(x); y = find(y);
        if(x==y) return;
        if(sz[x]>sz[y]) swap(x,y);
        sz[y] += sz[x];
        par[x] = y;
    }
    bool same(int x,int y){return find(x)==find(y);}
    void merge(int child,int parent){
        //parentが親,merge過程を表す木などで使用
        child = find(child); parent = find(parent);
        if(child==parent) return;
        mergeTree[parent].push_back(child);
        sz[parent] += sz[child];
        par[child] = parent;
    }
};

#include <atcoder/modint>
#include <string>

using namespace atcoder;
using mint = modint998244353;

string s[510];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
string dir = "RULD";
int main(){
    int i,j,k,h,w; cin >> h >> w;
    for(i=0;i<h;i++) cin >> s[i];
    UF uf1(h*w), uf2(4*h*w);
    auto isIn = [&](int x,int y){
        if(0<=x && x<h & 0<=y && y<w && s[x][y]=='#') return true;
        return false;
    };
    auto calc_from = [&](char c,int x,int y){
        if(c=='R') return x*w + y;
        if(c=='U') return x*w + y + h*w;
        if(c=='L') return x*w + y + 2*h*w;
        if(c=='D') return x*w + y + 3*h*w;
        return -1;
    };
    auto calc_to = [&](char c,int x,int y){
        if(c=='R') return x*w + y + 2*h*w;
        if(c=='U') return x*w + y + 3*h*w;
        if(c=='L') return x*w + y;
        if(c=='D') return x*w + y + h*w;
        return -1;
    };
    // 正方形を4領域に分ける
    // 隣接する場所は重み1
    // 向かい合う頂点同士の辺の重みは両方1 or 両方0
    // そのあと重み付きUFで頂点に色を付ける (黒白反転は同じなので、1/2する)
    for(i=0;i<h;i++){
        for(j=0;j<w;j++){
            if(!isIn(i,j)) continue;
            uf2.unite(calc_from('R',i,j),calc_from('L',i,j));
            uf2.unite(calc_from('U',i,j),calc_from('D',i,j));
            for(k=0;k<4;k++){
                int nx = i + dx[k],ny = j + dy[k];
                if(!isIn(nx,ny)) continue;
                uf1.unite(i*w + j,nx*w + ny);
                uf2.unite(calc_from(dir[k],i,j),calc_to(dir[k],nx,ny));
            }
        }
    }
    mint ans = 1;
    for(i=0;i<h;i++){
        for(j=0;j<w;j++){
            if(!isIn(i,j)) continue;
            ans *= 2;
            if(uf1.find(i*w + j)==i*w + j){
                // cout << i << " " << j << "\n";
                ans /= 2;
            }
        }
    }
    // cout << ans.val() << "\n";
    for(i=0;i<h;i++){
        for(j=0;j<w;j++){
            if(!isIn(i,j)) continue;
            for(k=0;k<4;k++){
                int x = calc_from(dir[k],i,j);
                if(uf2.find(x)==x){
                    // cout << i << " " << j << " " << k << " " << dir[k] << " " << x << "\n";
                    ans *= 2;
                }
            }
        }
    }
    cout << ans.val() << "\n";
}
0