Cod sursa(job #2777656)

Utilizator DavidAA007Apostol David DavidAA007 Data 23 septembrie 2021 20:34:06
Problema Pavare2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.91 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
ifstream fin("pavare2.in");
ofstream fout("pavare2.out");
int strada[155][20],strada1[155][20];
bool ok;
int v[205],viz[205];
int n,m,p,k,x,y,cate_pavele,lin,col;
void Bordare(int n, int m)
{
    for(int i=0;i<=n+1;i++)
    {
        strada[i][0]=1;
        strada[i][m+1]=1;
    }
    for(int j=0;j<=m+1;j++)
    {
        strada[0][j]=1;
        strada[n+1][j]=1;
    }
    for(int i=0;i<=n+1;i++)
    {
        strada1[i][0]=1;
        strada1[i][m+1]=1;
    }
    for(int j=0;j<=m+1;j++)
    {
        strada1[0][j]=1;
        strada1[n+1][j]=1;
    }
}
int estesolutie()
{
    for(int l=1;l<=n;l++)
    {
        for(int u=1;u<=m;u++)
        {
            strada1[l][u]=strada[l][u];
        }
    }
    bool verif=1;
    for(int l=1;l<=p;l++)
    {
        lin=v[l]/m+1;
        col=v[l]-(lin-1)*m;
        //cout<<lin<<" "<<col<<" "<<v[l]<<"\n";
        if(lin==n || col==m || v[l]%m==0)
        {
            verif=0;
            break;
        }
        strada1[lin][col]+=1;
        strada1[lin+1][col]+=1;
        strada1[lin][col+1]+=1;
        strada1[lin+1][col+1]+=1;
        if(strada1[lin][col]==2)
        {
            verif=0;
            break;
        }
        if(strada1[lin+1][col]==2)
        {
            verif=0;
            break;
        }
        if(strada1[lin][col+1]==2)
        {
            verif=0;
            break;
        }
        if(strada1[lin+1][col+1]==2)
        {
            verif=0;
            break;
        }
    }
    //cout<<"\n\n";
    return verif;
}
void Comb(int k)
{
    if(k-1==p)///vectorul este plin
    {
        if(estesolutie())
        {
            ok=1;
            //cout<<lin<<" "<<col<<" "<<v[p]<<" INTRA1\n";
            /*for(int i=1;i<=p;i++)
                cout<<v[i]<<" ";
            cout<<"\n\n";*/
            /*for(int l=1;l<=n;l++)
            {
                for(int u=1;u<=m;u++)
                {
                    cout<<strada1[l][u]<<" ";
                }
                cout<<"\n";
            }
            cout<<"\n\n";*/
        }
        /*for(int i=1;i<=p;i++)
            cout<<v[i]<<" ";
        cout<<"\n";*/
    }
    if(k-1!=n)
    {
        for(int i=v[k-1]+1;i<=n*m;i++)
        {
            if(viz[i]==0 && ok==0)
            {
                v[k]=i;//verificam daca locul este ocupat
                viz[i]=1;
                Comb(k+1);
                viz[i]=0;
            }
        }
    }
}
int main()
{
    fin>>n>>m>>k;
    Bordare(n,m);
    for(int q=1;q<=k;q++)
    {
        fin>>x>>y;
        strada[x][y]=1;
        strada1[x][y]=1;
    }
    int numartotal=(n*m-k)/4;
    for(p=numartotal;p>=1;p--)
    {
        k=1;
        ok=0;
        Comb(k);
        if(ok==1)
        {
            fout<<p<<"\n";
            break;
        }
    }
    fin.close();
    fout.close();
    return 0;
}
/*
 4 6 3
 1 1
 2 6
 3 3
 
 5 7 7
 1 5
 2 4
 3 2
 4 1
 5 1
 5 4
 5 6
 */