aoc2024 day14 p2

day14p2.cpp

#include <iostream>
#include <string>
#include <vector>
#include <cstdio>

using namespace std;
#define mkp make_pair
#define sz(x) ((int)x.size())
int test = 0;

int x_size=101;
int y_size=103;

struct Record{
    long x,y,vx,vy;
};
vector<Record> records;
struct Solver{
    int mat[105][105]={0};
    int vis[105][105]={0};
    int components=0;
    int oob(int x,int y){
        if(x<0||x>=x_size) return 1;
        if(y<0||y>=y_size) return 1;
        return 0;
    }
    void dfs(int x,int y){
        if(oob(x,y)) return;
        if(mat[x][y]==0) return;
        if(vis[x][y]) return;
        vis[x][y]=1;
        for(int i=-1;i<=1;i++)
            for(int j=-1;j<=1;j++)
                dfs(x+i,y+j);

    }
    void solve(){
            for(int i=0;i<x_size;i++){
                for(int j=0;j<y_size;j++){
                    if(mat[i][j]&&!vis[i][j]) {
                        dfs(i,j);
                        components++;
                    }
                }
            }
    }
};
int cnt[2][2];
int main()
{
    long p1=0,p2=0;
    string line;
    while(getline(cin,line)){
        Record tmp;
        sscanf(line.c_str(),"p=%ld,%ld v=%ld,%ld",&tmp.x,&tmp.y,&tmp.vx,&tmp.vy);
        records.push_back(tmp);
    }
    long best=9999;
    for(int iter=1;iter<=100000;iter++){
        Solver solver;
        for(auto &e:records){
            e.x= (e.x+x_size+e.vx)%x_size;
            e.y= (e.y+y_size+e.vy)%y_size;
            solver.mat[e.x][e.y]=1;
        }
        solver.solve();
        if(solver.components<best){
            best=solver.components;
            printf("====== iter=%d components=%d =======\n", iter, solver.components);
            for(int i=0;i<x_size;i++){
                for(int j=0;j<y_size;j++){
                    if(solver.mat[i][j]) printf("xx");
                    else printf(" ");
                }
                printf("\n");
            }
        }
        if(iter==100){
            for(auto &e:records){
                if (e.x ==(x_size)/2) continue;
                if (e.y==(y_size)/2) continue;
                cnt[e.x < (x_size)/2][ e.y <(y_size)/2]++;
            }
        }
    }

    cout<<cnt[0][0]<<" "<<cnt[0][1]<<endl;
    cout<<cnt[1][0]<<" "<<cnt[1][1]<<endl;
    cout<<"p1="<<cnt[0][0]*cnt[0][1]*cnt[1][0]*cnt[1][1]<<endl;
    return 0;
}

input data:
https://gist.github.com/wangyu-/10f031af211f05dc7394199e48992a54