Submission #1150990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150990		koukirocks	Dango Maker (JOI18_dango_maker)	C++20	13 / 100	1 ms	328 KiB

dango_maker

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) x.begin(), x.end()
#define F first
#define S second

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const ll oo=0x3f3f3f3f3f3f3f3f;

const int dir[2][2]={{0,1},{1,0}};
char mp[3010][3010];
bool iss[3010][3010][2];
int vis[3010][3010][2];
string s="RGW";
int n,m;

bool is(int i,int j,int d) {
    // cout<<i<<" "<<j<<" "<<d<<" ijd\n";
    if (i<=0 or j<=0) return false;
    for (int k=0;k<=2;k++) {
        // cout<<k<<" k\n";
        if (i>n or j>m) return false;
        if (mp[i][j]!=s[k]) return false;
        // cout<<i<<" "<<j<<" "<<mp[i][j]<<" "<<s[k]<<" ij mp s\n";
        i+=dir[d][0];j+=dir[d][1];
    }
    return true;
}

struct Node {
    int x,y,d;
};

int BFS(int x,int y,int d) {
    queue<Node> Q;
    int cnt[2]={0,0};
    Q.push({x,y,d});
    vis[x][y][d]=true;
    while (!Q.empty()) {
        Node v=Q.front();
        Q.pop();
        // cout<<v.x<<" "<<v.y<<" "<<v.d<<" v\n";
        int rd=1-v.d;
        cnt[v.d]++;
        for (int k=0;k<=2;k++) {
            int nx=v.x+k*(dir[v.d][0]-dir[rd][0]);
            int ny=v.y+k*(dir[v.d][1]-dir[rd][1]);
            if (nx<=0 or ny<=0 or nx>n or ny>m) continue;
            if (vis[nx][ny][rd]) continue;
            if (iss[nx][ny][rd]) {
                Q.push({nx,ny,rd});
                vis[nx][ny][rd]=true;
            }
        }
    }
    // cout<<"\n";
    return max(cnt[0],cnt[1]);
}

int main() {
    speed;
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            cin>>mp[i][j];
        }
    }
    ll ans=0;
    // for (int i=1;i<=n;i++) {
    //     for (int j=1;j<=m;j++) {
    //         cout<<mp[i][j]<<" ";
    //     }
    // }
    // cout<<is(1,1,0)<<" "<<is(1,1,1)<<" is\n";
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            for (int d=0;d<=1;d++) {
                vis[i][j][d]=false;
                iss[i][j][d]=is(i,j,d);
            }
        }
    }
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            for (int d=0;d<=1;d++) {
                if (vis[i][j][d]) continue;
                if (iss[i][j][d]) {
                    ans+=BFS(i,j,d);
                }
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}





/*
7 9
WWWWWWRGW
WWWWWRGWW
WWWWRGWWW
WWWWGWWWW
WWRGWWWWW
WRGWWWWWW
RGWWWWWWW
*/

• Subtask 1: 13 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67