Coloring Grids

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

int n,m;
string og[101010], ans[101010];
vector<int> vis[101010];
vector<set<int>> pos[101010];

bool change(int i,int j) {
    set<char> posi;
    posi.insert('1');
    posi.insert('2');
    posi.insert('3');
    posi.insert('4');
    posi.erase(og[i][j]);
    for (int ii=-1;ii<=1;ii++) {
        for (int jj=-1;jj<=1;jj++) {
            if (abs(ii+jj)==1) {
                if (i+ii>=0 && i+ii<n && j+jj>=0 && j+jj<m) posi.erase(og[i+ii][j+jj]);
            }
        }
    }
    if (posi.empty()) return false;
    char t=(*posi.begin());
    og[i][j]=t;
    return true;
}

void bfs() {
    vector<pair<pair<int,int>,pair<int,int>>> v;
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            if (og[i][j]=='0') {
                for (int ii=-1;ii<=1;ii++) {
                    for (int jj=-1;jj<=1;jj++) {
                        if (abs(ii+jj)==1) {
                            if (i+ii>=0 && i+ii<n && j+jj>=0 && j+jj<m) {
                                if (og[i+ii][j+jj]!='0' && !vis[i+ii][j+jj]) {
                                    vis[i+ii][j+jj]=1;
                                    v.push_back({{i+ii,j+jj},{-1,-1}});
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    
    for (int k=0;k<(int)v.size();k++) {
        if (change(v[k].F.F,v[k].F.S)) {
            pair<int,int> prev=v[k].S;
            for (int kk=k-1;kk>=0;kk--) {
                if (v[kk].F==prev) {
                    assert(change(v[kk].F.F,v[kk].F.S));
                    prev=v[kk].S;
                }
            }
            return;
        } else {
            int i=v[k].F.F;
            int j=v[k].F.S;
            for (int ii=-1;ii<=1;ii++) {
                for (int jj=-1;jj<=1;jj++) {
                    if (abs(ii+jj)==1) {
                        if (i+ii>=0 && i+ii<n && j+jj>=0 && j+jj<m) {
                            if (og[i+ii][j+jj]!='0' && !vis[i+ii][j+jj]) {
                                vis[i+ii][j+jj]=1;
                                v.push_back({{i+ii,j+jj},{i,j}});
                            }
                        }
                    }
                }
            }
        }
    }
}

bool solve() {
    for (int i=0;i<n;i++) {
        pos[i].clear();
        ans[i]=og[i];
        for (int j=0;j<m;j++) {
            pos[i].push_back({});
        }
    }
    priority_queue<pair<int,pair<int,int>>> pq;
    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            if (og[i][j] == '0') {
                for (int k=0;k<4;k++) pos[i][j].insert('1'+k);
                for (int ii=-1;ii<=1;ii++) {
                    for (int jj=-1;jj<=1;jj++) {
                        if (abs(ii+jj)==1) {
                            if (i+ii>=0 && i+ii<n && j+jj>=0 && j+jj<m) pos[i][j].erase(og[i+ii][j+jj]);
                        }
                    }
                }
                pq.push({-(int)pos[i][j].size(),{i,j}});
            }
        }
    }
    while (!pq.empty()) {
        auto xx = pq.top();
 //       cerr<<xx.F<<" "<<xx.S.F<<" "<<xx.S.S<<endl;
        pq.pop();
        if (ans[xx.S.F][xx.S.S]!='0') continue;
        int i= xx.S.F;
        int j=xx.S.S;
        if (pos[i][j].size()==0) return false;
        vector<int> v;
        for (int k=0;k<4;k++) v.push_back(0);
        for (int ii=-1;ii<=1;ii++) {
            for (int jj=-1;jj<=1;jj++) {
                if (abs(ii+jj)==1) {
                    if (i+ii>=0 && i+ii<n && j+jj>=0 && j+jj<m) {
                        if (ans[i+ii][j+jj]=='0') {
                            for (int k=0;k<4;k++) v[k]++;
                            for (char c : pos[i+ii][j+jj]) v[c-'1']--;
                        } else {
                            v[ans[i+ii][j+jj]-'1'] = -1;
                        }
                    }
                }
            }
        }
        char parsa='1';
        int maxef=-1;
        for (char c : pos[i][j]) {
//            cerr<<c<<endl;
//            cerr<<v[c-'1']<<endl;
            if (v[c-'1']>maxef) {
                maxef = v[c-'1'];
                parsa = c;
//                cerr<<i<<" "<<j<<" "<<parsa<<" "<<maxef<<endl;
            }
        }
        ans[i][j]=parsa;
        for (int ii=-1;ii<=1;ii++) {
            for (int jj=-1;jj<=1;jj++) {
                if (abs(ii+jj)==1) {
                    if (i+ii>=0 && i+ii<n && j+jj>=0 && j+jj<m) {
                        if (ans[i+ii][j+jj]=='0' && pos[i+ii][j+jj].count(parsa)) {
                            pos[i+ii][j+jj].erase(parsa);
                            pq.push({-(int)pos[i+ii][j+jj].size(),{i+ii,j+jj}});
                        }
                    }
                }
            }
        }
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for (int i=0;i<n;i++) {
        cin>>og[i];
        for (int j=0;j<m;j++) {
            vis[i].push_back(0);
        }
    }
    if (solve()) {
//        cerr<<"MOI"<<endl;
        for (int i=0;i<n;i++) {
            cout<<ans[i]<<"\n";
        }
        return 0;
    }
    bfs();
    solve();
    for (int i=0;i<n;i++) {
        cout<<ans[i]<<"\n";
    }
    
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED

Test 60

Verdict: ACCEPTED

Test 61

Verdict: ACCEPTED

Test 62

Verdict: ACCEPTED

Test 63

Verdict: ACCEPTED

Test 64

Verdict: ACCEPTED

Test 65

Verdict: ACCEPTED