头像

贴着土地生活


访客:2128

离线:6小时前



算法1

区间dp, 分三种情况转移即可

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
#include<string>
using namespace std;

const int N = 1010;

int f[N][N];

int n;

string s;

int main()
{
    memset(f, 0x3f, sizeof f);
    cin >> s;
    int len = s.size();
    for(int i = 0; i < len; ++ i)
        f[i][i] = 0;
    for(int k = 2; k <= len; ++ k)
        for(int i = 0; i < len; ++ i)
                {
                    int j = i - k + 1;
                    if(j < 0) continue;
                    int &v = f[j][i];
                    int l = j, r = i;
                    while(s[l] == s[r]) -- r, ++ l;
                    if(l > r) v = 0;
                    else
                    {
                        v = min(v, f[l][r]);
                        v = min(v, f[j + 1][i] + 1);
                        v = min(v, f[j][i - 1] + 1);    
                    }
                }
    printf("%d", f[0][len - 1]);
    return 0;
}



算法1

空间换时间的优化,四重循环变二重

C++ 代码

#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

const int N = 2500;

PII mp[5000010];

int st[5000010];

int mi[N];

int n;

int main()
{
    cin >> n;
    int maxv = sqrt(n);
    for(int i = 1; i <= maxv; ++ i)
        mi[i] = i * i;
    for(int i = 0; i <= maxv; ++ i)
        for(int j = i; j <= maxv; ++ j)
            if(mi[i] + mi[j] <= n && !st[mi[i] + mi[j]])
                {
                    mp[mi[i] + mi[j]] = {i, j};
                    st[mi[i] + mi[j]] = 1;
                }
    int a, b, c, d;
    for(int i = 0; i <= maxv; ++ i)
        for(int j = i; j <= maxv; ++ j)
            if(st[n - mi[i] - mi[j]])
                {
                    PII t = mp[n - mi[i] - mi[j]];
                    a = i, b = j, c = t.x, d = t.y;
                    printf("%d %d %d %d", a, b, c, d);
                    return 0;
                }
    return 0;
}



#include<iostream>
#include<cstring>
#include<string>
#include<set>
#include<algorithm>

using namespace std;

const int N = 10;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int g[N][N];

int stat[N][N];

int bstat[N][N];

int isvst[N][N];

string s;

set<string> st;

int sum;

int res;

class CHK
{
    public:
    int sum, cnt;
};


struct Point{
    int x, y, w;
    bool operator<(Point &b){
        return w < b.w;
    }
}points[N * N];

int idx;

int n, m;

CHK flood(int i, int j)
{
    int sum = g[i][j], cnt = 1;
    isvst[i][j] = 1;
    CHK v = {sum, cnt};
    for(int k = 0; k < 4; ++ k)
    {
        int ix = i + dx[k], iy = j + dy[k];
        if(ix < 0 || iy < 0 || ix >= n || iy >= m) continue;
        if(isvst[ix][iy]) continue;
        if(stat[ix][iy] != stat[i][j]) continue;
        CHK rt = flood(ix, iy);
        v.cnt += rt.cnt, v.sum += rt.sum;
    }
    return v;
}

void fld(int i, int j)
{
    isvst[i][j] = true;
    for(int k = 0; k < 4; ++ k)
    {
        int ix = i + dx[k], iy = j + dy[k];
        if(ix < 0 || iy < 0 || ix >= n || iy >= m)  continue;
        if(stat[ix][iy] != stat[i][j]) continue;
        if(isvst[ix][iy]) continue;
        fld(ix, iy);
    }   
}

int getpart()
{
    int partnum = 0;
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
            if(!isvst[i][j])
            {
                fld(i, j);
                partnum ++;
            }
    return partnum;
}

bool check(int cnt)
{
    memset(isvst, 0, sizeof isvst);
    int part = getpart();
    if(part != 2) return false;
    memset(isvst, 0, sizeof isvst);
    CHK v = flood(0, 0);
    if((v.sum == sum / 2) && (v.cnt == cnt || (v.cnt == m * n - cnt))) 
        return true;
    return false;
}

void dfs(int curs, int cnt)
{
    if(st.count(s)) return;
    if(cnt >= res) return;
    if(curs >= sum / 2)
    {
        if(check(cnt)){
            //int temp = res;
            res = min(res, stat[0][0] ? cnt : (n * m - cnt));
            //if(res < temp) memcpy(bstat, stat, sizeof stat);
        }
        return;
    }
    st.insert(s);
    for(int i = 0; i < m * n; ++ i)
    {
        if(s[i] == '0') 
        {
            int x = points[i].x, y = points[i].y;
            s[i] = s[i] + 1;
            stat[x][y] = 1;
            dfs(curs + g[x][y], cnt + 1);
            s[i] = s[i] - 1;
            stat[x][y] = 0;
        }
    }       
}

int main()
{
    scanf("%d%d", &m, &n);
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
            {
                cin >> g[i][j];
                sum += g[i][j];
            }
    for(int i = 0; i < m * n; ++ i)
        s += '0';

    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < m; ++ j)
            points[idx ++ ] = {i, j, g[i][j]};
    sort(points, points + m * n);
    res = 0x3f3f3f3f;
    dfs(0, 0);
    if(res < 0x3f3f3f3f) printf("%d\n", res);
    else printf("%d", 0);
    /*  for(int i = 0; i < n; ++ i)
        {
            for(int j = 0; j < m; ++ j)
                printf("%d ", bstat[i][j]);
            printf("\n");
        }*/
    return 0;
}



算法1

floodfill
#include<iostream>
#include<cstring>
using namespace std;

const int N = 1010;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

char g[N][N];

bool st[N][N];

int n;

bool dfs(int x, int y)
{
    st[x][y] = true;
    bool tag1 = true;
    bool tag2 = false;
    for(int k = 0; k < 4; ++ k)
    {
        int ix = x + dx[k], iy =  y + dy[k];
        if(ix < 0 || iy < 0 || ix >= n || iy >= n) continue;
        if(g[ix][iy] == '.')
        {
            tag2 = true;
            continue;
        }
        if(st[ix][iy]) continue;
        if(g[ix][iy] == '#')
        {
            tag1 &= dfs(ix, iy);
        }
    }
    return tag1 && tag2;
}

int main()
{
    cin >> n;
    int cnt = 0;
    for(int i = 0; i < n; ++ i)
        scanf("%s", g[i]);
    for(int i = 0; i < n; ++ i)
        for(int j = 0; j < n; ++ j)
            if(g[i][j] == '#' && !st[i][j]) 
                if(dfs(i, j)) ++ cnt;
    printf("%d", cnt);
    return 0;
}



题目描述


算法1 2-sat算法,思路分分钟,写代码20分钟,然而各种细节调了一下午

C++ 代码

#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;

#define a first
#define b second

typedef pair<int, int> PII;

const int N = 210, M = 10010;

PII edges[M];

int st[2 * M]; // is in loop

//tarjan
int dfn[M * 2], low[M * 2], ts, stk[M * 2], top, ins[M * 2];
int id[M * 2], cnt;

int h[M * 2], e[2000010], ne[2000010], idx;

int mp[N];

int n, m;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++; 
}

bool is_cross(int i, int j)//check if two edges cross
{
    int ia = mp[edges[i].a], ib = mp[edges[i].b];
    if(ia > ib) swap(ia, ib);
    int ja = mp[edges[j].a], jb = mp[edges[j].b];
    if(ja > jb) swap(ja, jb);
    if(ia < ja && ib < jb && ib > ja) return true;
    if(ja < ia && jb < ib && jb > ia) return true; 
    return false;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ ts;
    stk[++ top ] = u, ins[u] = true;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if(ins[j]) low[u] = min(dfn[j], low[u]);
    }
    if(dfn[u] == low[u])
    {
        ++ cnt;
        int k;
        do{
            k = stk[top --];
            ins[k] = false;
            id[k] = cnt;
        }while(k != u);
    }
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t --)
    {
        scanf("%d%d", &n, &m);
        memset(h, -1, sizeof h);
        memset(st, 0, sizeof st);
        memset(mp, 0, sizeof mp);
        memset(dfn, 0, sizeof dfn);
        memset(low, 0, sizeof low);
        memset(id, 0, sizeof id);
        ts = 0, cnt = 0;
        idx = 0;
        for(int i = 1; i <= m; ++ i)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            edges[i] = {a, b};
        }
        for(int i = 1; i <= n; ++ i)
        {
            int x;
            scanf("%d", &x);
            mp[x] = i;  
        }
        if(m > (n * 3 - 6))
        {
            puts("NO");
            continue;
        }
        for(int i = 1; i <= m; ++ i)
        {
            int a = edges[i].a, b = edges[i].b;
            if((abs(mp[a] - mp[b]) == 1) || (abs(mp[a] - mp[b]) == n - 1)) 
                st[i] = true, st[i + m] = true; 
        }
        //for(int i = 1; i <= m; ++ i) 
        //  printf("%d %d %d %d\n", i, edges[i].a, edges[i].b, st[i]);
        for(int i = 1; i <= m; ++ i)
            if(st[i]) continue;
            else 
                for(int j = 1; j < i; ++ j)
                    if(st[j]) continue;
                    else if(is_cross(i, j))
                    {
                        //printf("%d %d\n", i, j);
                        add(i, j + m), add(j, i + m);
                        add(i + m, j), add(j + m, i);
                    }
        for(int i = 1; i <= 2 * m; ++ i)
            if(!st[i] && !dfn[i])
                tarjan(i);
        bool tag = true;
        //for(int i = 1; i <= 2 * m; ++ i)
        //  printf("%d ", id[i]);
        for(int i = 1; i <= m; ++ i)
            if(!st[i] && id[i] == id[i + m])
                {
                    tag = false;
                    break;  
                }
        if(tag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}



#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;

#define a first
#define b second

typedef pair<int, int> PII;

const int N = 210, M = 10010;

PII edges[M];

int st[M]; // is in loop

//tarjan
int dfn[M * 2], low[M * 2], ts, stk[M * 2], top, ins[M * 2];
int id[M * 2], cnt;

int h[M * 2], e[97000010], ne[97000010], idx;

int mp[N];

int n, m;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++; 
}

bool is_cross(int i, int j)//check if two edges cross
{
    int ia = mp[edges[i].a], ib = mp[edges[i].b];
    if(ia > ib) swap(ia, ib);
    int ja = mp[edges[j].a], jb = mp[edges[j].b];
    if(ja > jb) swap(ja, jb);
    if(ia < ja && ib < jb && ib > ja) return true;
    if(ja < ia && jb < ib && jb > ia) return true; 
    return false;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ ts;
    stk[++ top ] = u, ins[u] = true;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if(ins[j]) low[u] = min(dfn[j], low[u]);
    }
    if(dfn[u] == low[u])
    {
        ++ cnt;
        int k;
        do{
            k = stk[top --];
            ins[k] = false;
            id[k] = cnt;
        }while(k != u);
    }
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t --)
    {
        scanf("%d%d", &n, &m);
        memset(h, -1, sizeof h);
        memset(st, 0, sizeof st);
        memset(mp, 0, sizeof mp);
        memset(dfn, 0, sizeof dfn);
        memset(low, 0, sizeof low);
        memset(id, 0, sizeof id);
        ts = 0, cnt = 0;
        for(int i = 1; i <= m; ++ i)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            edges[i] = {a, b};
        }
        for(int i = 1; i <= n; ++ i)
        {
            int x;
            scanf("%d", &x);
            mp[x] = i;  
        }

        for(int i = 1; i <= m; ++ i)
        {
            int a = edges[i].a, b = edges[i].b;
            if((abs(mp[a] - mp[b]) == 1) || (abs(mp[a] - mp[b]) == n - 1)) 
                st[i] = true, st[i + m] = true; 
        }
        //for(int i = 1; i <= m; ++ i) 
        //  printf("%d %d %d %d\n", i, edges[i].a, edges[i].b, st[i]);
        for(int i = 1; i <= m; ++ i)
            if(st[i]) continue;
            else 
                for(int j = 1; j < i; ++ j)
                    if(st[j]) continue;
                    else if(is_cross(i, j))
                    {
                        //printf("%d %d\n", i, j);
                        add(i, j + m), add(j, i + m);
                        add(i + m, j), add(j + m, i);
                    }
        for(int i = 1; i <= 2 * m; ++ i)
            if(!st[i] && !dfn[i])
                tarjan(i);
        bool tag = true;
        //for(int i = 1; i <= 2 * m; ++ i)
        //  printf("%d ", id[i]);
        for(int i = 1; i <= m; ++ i)
            if(!st[i] && id[i] == id[i + m])
                {
                    tag = false;
                    break;  
                }
        if(tag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}


活动打卡代码 AcWing 1064. 小国王

#include<iostream>
#include<cstring>
using namespace std;

typedef long long LL;

const int N = 11;

LL f[N][N * N][1 << N];

int lowbit(int x)
{
    return x & -x;
}

int count1(int x)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i))
        res ++;
    return res;
}

int n, k;

int main()
{
    cin >> n >> k;
    for(int i = 0; i <= k; ++ i)
        for(int j = 0; j < 1 << n; ++ j)
            if(((j << 1) & j) || ((j >> 1) & j)) continue;
            else f[1][i][j] = count1(j) == i ? 1 : 0;
    for(int i = 2; i <= n; ++ i)
        for(int j = 0; j <= k; ++ j)
            for(int t = 0; t < 1 << n; ++ t)
                if(((t << 1) & t) || ((t >> 1) & t))
                    continue;
                else if(j >= count1(t))
                {
                    for(int h = 0; h < 1 << n; ++ h)
                        if(((h << 1) & h) || ((h >> 1) & h)) continue;
                        else if((h & t) || ((h << 1) & t) || ((h >> 1) & t)) continue;
                        else f[i][j][t] += f[i - 1][j - count1(t)][h];
                }
    LL res = 0;
    for(int i = 0; i < 1 << n; ++ i)
        res += f[n][k][i];
    cout << res;
    return 0;
}




算法1

DFS加等效冗余剪枝(顺便吐槽,1个int敲成了bool调了快一小时屮屮)

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 10;

int n;

int g[5][7];

int st[5][7];

struct op{
    int x, y, t;
}path[N], res[N];

int idx;

bool is_leaf()
{
    bool tag = true;
    for(int i = 0; i < 5; ++ i)
        if(g[i][0])
            tag = false;
    return tag;
}

bool check_line(int x, int y)
{
    int len = 1;
    for(int i = 1; x - i >= 0; ++ i)
    if(g[x - i][y] == g[x][y]) ++ len; else break;

    for(int i = 1; x + i < 5; ++ i)
    if(g[x + i][y] == g[x][y]) ++ len; else break;

    return len >= 3;
}

void set_line(int x, int y)
{
    st[x][y] = 1;
    for(int i = 1; x - i >= 0; ++ i)
    if(g[x - i][y] == g[x][y]) st[x - i][y] = 1; else break;

    for(int i = 1;x + i < 5; ++ i)
    if(g[x + i][y] == g[x][y]) st[x + i][y] = 1; else break;
}

bool check_col(int x, int y)
{
    int len = 1;
    for(int i = 1; y - i >= 0; ++ i)
    if(g[x][y - i] == g[x][y]) ++ len; else break;

    for(int i = 1; y + i < 7; ++ i)
    if(g[x][y + i] == g[x][y]) ++ len; else break;

    return len >= 3;
}

void set_col(int x, int y)
{
    st[x][y] = 1;
    for(int i = 1; y - i >= 0; ++ i)
    if(g[x][y - i] == g[x][y]) st[x][y - i] = 1; else break;

    for(int i = 1; y + i < 7; ++ i) 
    if(g[x][y + i] == g[x][y]) st[x][y + i] = 1; else break;
}

void mark()
{
    memset(st, 0, sizeof st);
    for(int i = 0; i < 5; ++ i)    
        for(int j = 0; j < 7; ++ j)
            {
                if(!g[i][j]) continue;
                if(check_line(i, j)) set_line(i, j);
                if(check_col(i, j)) set_col(i, j);
            }
}

int remove()
{
    int cnt = 0;
    for(int i = 0; i < 5; ++ i)    
        for(int j = 0; j < 7; ++ j)
            if(st[i][j])
                g[i][j] = 0, ++ cnt;
    return cnt;
}

void processing(int arr[])
{
    int i = 0, j = 0;
    while(i < 7 && arr[i]) ++ i, ++ j;
    while(j < 7)
    {
        if(arr[j]) swap(arr[i], arr[j]), ++ i, ++ j;
        else ++ j;
    }
}

void drop()
{
    for(int i = 0; i < 5; ++ i) 
        processing(g[i]);
}

void update()//1 右移  -1 左移
{
    mark();
    if(!remove()) return;
    drop();
    update();
}


bool dfs(int x, int y, int t, int k)
{
    int bg[5][7];
    memcpy(bg, g, sizeof g);
    if(k > n) return false;
    if(x + t < 0 || x + t >= 5) return false;
    swap(g[x][y], g[x + t][y]);
    drop();//!!!!!!
    update();
    path[idx ++ ] = {x, y, t};
    if(is_leaf() && k == n) 
    {
        memcpy(res, path, sizeof res);    
        memcpy(g, bg, sizeof g);
        -- idx;
        return true;    
    }
    for(int i = 0; i < 5; ++ i)
        for(int j = 0; j < 7; ++ j)
            if(g[i][j])
                {
                    if(dfs(i, j, 1, k + 1))
                    {
                        memcpy(g, bg, sizeof bg);
                        -- idx;
                        return true;
                    }
                    if(i > 0 && !g[i - 1][j]) 
                        if(dfs(i, j, -1, k + 1))
                        {
                            memcpy(g, bg, sizeof bg);
                            -- idx;
                            return true;
                        }
                }
    memcpy(g, bg, sizeof bg);
    -- idx;
    return false;
}



int main()
{

    cin >> n;
    for(int i = 0; i < 5; ++ i)
    {
        for(int j = 0; j < 8; ++ j)
        {
            int x;
            cin >> x;
            if(!x) break;
            g[i][j] = x;
        }
    }

    bool tag = false;
    for(int i = 0; i < 5; ++ i)
        {
            for(int j = 0; j < 7; ++ j)
            {
                if(g[i][j])
                {
                    if(dfs(i, j, 1, 1)){ tag = true; break; }
                    if(i > 0 && !g[i - 1][j])
                        if(dfs(i, j, -1, 1))
                            { tag = true; break; }
                }
            }
            if(tag) break;
        }

    if(tag) 
    {
        for(int i = 0; i < n; ++ i) 
        printf("%d %d %d\n", res[i].x, res[i].y, res[i].t);
    }
    else printf("%d", -1);

    return 0;
}



#include<iostream>
#include<cstring>
#include<bitset>
using namespace std;

const int N = 310, M = 610;

bitset<310> infect;

int n, p;

int res;

int h[N], ne[M], e[M], idx;

int d[N], q[N];

int cut[M];//当前边是否已被切断

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int ext()
{
    int num = 0;
    bitset<310> temp;
    for(int u = 1; u <= n; ++ u)
    {
        if(!infect[u]) continue;
        for(int i = h[u]; ~i; i = ne[i])
        {
            if(cut[i]) continue;
            int j = e[i];
            if(!infect[j])
            {
                ++ num;
                temp[j] = 1;
            }
        }
    }
    infect |= temp;
    return num;
}

int inc()
{
    int num = 0;
    for(int u = 1; u <= n; ++ u)
    {
        if(!infect[u]) continue;
        for(int i = h[u]; ~i; i = ne[i])
        {
            if(cut[i]) continue;
            int j = e[i];
            if(!infect[j])
            {
                ++ num;
            }
        }
    }
    return num;
}

void dfs(int cnt)
{
    if(cnt >= res) return;
    if(inc() == 0) 
    {
        res = cnt;
        return;
    }
    for(int u = 1; u <= n; ++ u)
    {
        if(!infect[u]) continue;
        for(int i = h[u]; ~i; i = ne[i])
        {
            if(cut[i]) continue;
            int j = e[i];
            //if(d[j] < d[u]) continue;
            if(infect[j]) continue;
            cut[i] = true;
            bitset<310> bake = infect;
            int num = ext();
            //cout << infect << endl;
            //cout << num << endl;
            dfs(cnt + num);
            cut[i] = false;
            infect = bake;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &p);
    infect[1] = 1;
    memset(h, -1, sizeof h);
    for(int i = 0; i < p; ++ i)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    //bfs();
    res = 0x3f3f3f3f;
    dfs(1);
    printf("%d", res);
    return 0;
}


活动打卡代码 AcWing 166. 数独

#include<iostream>
#include<cstring>
using namespace std;

const int N = 9;

int g[N][N];
int res[N][N];
int st[10];

string s;

int get(int x, int y)
{
    memset(st, 0, sizeof st);
    for(int i = 0; i < 9; ++ i)
        if(g[x][i]) st[g[x][i]] = true;
    for(int i = 0; i < 9; ++ i)
        if(g[i][y]) st[g[i][y]] = true;
    for(int i = x / 3 * 3; i < x / 3 * 3 + 3; ++ i)
        for(int j = y / 3 * 3; j < y / 3 * 3 + 3; ++ j)
            if(g[i][j]) st[g[i][j]] = true;
    int res = 0;
    for(int i = 1; i <= 9; ++ i)
        if(!st[i])
            ++ res;
    return res;
}

bool check(int x, int y, int k)
{
    bool tag = true;
    for(int i = 0; i < 9; ++ i)
        if(g[x][i] == k) tag = false;
    for(int i = 0; i < 9; ++ i)
        if(g[i][y] == k) tag = false;
    for(int i = x / 3 * 3; i < x / 3 * 3 + 3; ++ i)
        for(int j = y / 3 * 3; j < y / 3 * 3 + 3; ++ j)
            if(g[i][j] == k)
                tag = false;
    return tag;
}

bool dfs(int x, int y, int k, int cnt) 
{
    if(!check(x, y, k)) return false;
    if(cnt == 0) 
    {
        g[x][y] = k;
        memcpy(res, g, sizeof res);
        g[x][y] = 0;
        return true;
    }
    g[x][y] = k;
    int nx = 0, ny = 0;
    int t = 0x3f3f3f3f;
        for(int i = 0; i < 9; ++ i)
            for(int j = 0; j < 9; ++ j)
                {
                    if(!g[i][j] && get(i, j) < t)
                        t = get(i, j), nx = i, ny = j;
                }
    for(int i = 1; i <= 9; ++ i)
        if(dfs(nx, ny, i, cnt - 1))
            {
                g[x][y] = 0;
                return true;
            }
    g[x][y] = 0;
    return false;
}

int main()
{
    while(cin >> s, s != "end")
    {
        int cnt = 81;
        memset(g, 0, sizeof g);
        for(int i = 0; i < 81; ++ i)
            if(s[i] != '.') g[i / 9][i % 9] = s[i] - '0', -- cnt;
        int x = 0, y = 0;
        int t = 0x3f3f3f3f;
        for(int i = 0; i < 9; ++ i)
            for(int j = 0; j < 9; ++ j)
                {
                    if(!g[i][j] && get(i, j) < t)
                        t = get(i, j), x = i, y = j;
                }
        for(int i = 1; i <= 9; ++ i)
            if(dfs(x, y, i, cnt - 1))
                break;
        for(int i = 0; i < 9; ++ i)
            for(int j = 0; j < 9; ++ j)
                printf("%d", res[i][j]);
        printf("\n");
    }
    return 0;