제출 #1150987

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150987		koukirocks	Dango Maker (JOI18_dango_maker)	C++20	13 / 100	38 ms	71240 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][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;
    bool flag=true;
    for (int k=0;k<=2;k++) {
        // cout<<k<<" k\n";
        if (i>n or j>m) return false;
        flag&=(mp[i][j]==s[k]);
        // cout<<i<<" "<<j<<" "<<mp[i][j]<<" "<<s[k]<<" ij mp s\n";
        i+=dir[d][0];j+=dir[d][1];
    }
    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][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) continue;
            if (vis[nx][ny][rd]) continue;
            if (is(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";
    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][d]) continue;
                if (is(i,j,d)) {
                    ans+=BFS(i,j,d);
                }
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}





/*
10 10
RGRWGRWRGR
GWGRWGRGGG
RGWRWGRRGW
WGRWGRWGRW
GWRGWRGWRW
GRWGRWRWGR
GWRGWRGWGW
RGRRGWRRGR
GWGGWRGGGG
RGWRGWRRGW
*/

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