Submission #1150969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150969		koukirocks	Dango Maker (JOI18_dango_maker)	C++20	13 / 100	15 ms	35912 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];
int vis[3010][3010];
string s="RGW";
int n,m;

bool is(int i,int j,int d) {
    if (i<=0 or j<=0) return false;
    bool flag=true;
    for (int k=0;k<=2;k++) {
        if (i+k*dir[d][0]>n or j+k*dir[d][1]>m) return false;
        flag&=(mp[i+k*dir[d][0]][j+k*dir[d][1]]==s[k]);
    }
    return flag;
}

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]|=(1<<d);
    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) continue;
            if (vis[nx][ny]&(1<<rd)) continue;
            if (is(nx,ny,rd)) {
                Q.push({nx,ny,rd});
                vis[nx][ny]|=(1<<rd);
            }
        }
    }
    // 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;
    memset(vis,0,sizeof(vis));
    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]&(1<<d)) continue;
                if (is(i,j,d)) {
                    ans+=BFS(i,j,d);
                }
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}


/*
3 5
WWRGW
WRGWW
RGWWW
*/

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