Cod sursa(job #2303249)

Utilizator Vlad3108Tir Vlad Ioan Vlad3108 Data 15 decembrie 2018 21:56:38
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <bits/stdc++.h>
using namespace std;
int n,m,k;
bool Viz[35][35];
int A[35][35];
struct Point{
    int l,c;
    bool inside(){
        return 1<=l&&l<=n&&1<=c&&c<=m;
    }
}d[8]={{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}};
int Min=INT_MAX,ct_Min=0;
int best[7],st[7];
void Back(int level,Point X,int card){
    if(level==k+1) return ;
    if(card==0){
        if(level<Min){
            Min=level;
            ct_Min=1;
            for(int i=1;i<=Min;++i)
                best[i]=st[i];
        }
        else if(level==Min){
            ++ct_Min;
            if(st[Min]<best[Min]||(st[Min]==best[Min]&&st[1]<best[1]))
                for(int i=1;i<=Min;++i)
                    best[i]=st[i];
        }
        return ;
    }
    if(level==0) Viz[X.l][X.c]=1;
    Point Next;
    for(int i=0;i<8;++i){
        Next.l=X.l+d[i].l;
        Next.c=X.c+d[i].c;
        if(Next.inside()&&Viz[Next.l][Next.c]==0){
            int x=A[Next.l][Next.c];
            st[level+1]=x;
            Viz[Next.l][Next.c]=1;
            /// CASE 1
            Back(level+1,Next,card-2*x);
            /// CASE 2
            Back(level+1,Next,card-x/2);
            /// CASE 3
            Back(level+1,Next,card+x);
            /// CASE 4
            Back(level+1,Next,card-x);
            Viz[Next.l][Next.c]=0;
        }
    }
}
int main(){
    freopen("card.in","r",stdin);
    freopen("card.out","w",stdout);
    int x,y;
    scanf("%d %d %d %d %d",&n,&m,&x,&y,&k);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%d",&A[i][j]);
    Back(0,{x,y},A[x][y]);
    printf("%d\n",ct_Min);
    for(int i=1;i<=Min;++i)
        printf("%d ",best[i]);
    printf("\n");
    return 0;
}