Cod sursa(job #1164973)

Utilizator muscaTudose Vlad-Adrian musca Data 2 aprilie 2014 13:21:11
Problema Castel Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <cstdio>
#include <vector>
#include <bitset>
using namespace std;
int n,m,i,j,solution;
struct matrice
{
    int val;
    bitset<1> vizited;
};
matrice a[155][155];//nu este problema
vector<int> v[25505];
int curent_keys[25505];//nu este problema
struct coord
{
    int x,y,needed_key;
};
coord initial_pozition;
void read()
{
    scanf("%d%d%d", &n, &m, &initial_pozition.needed_key);
    if(initial_pozition.needed_key%m==0)
    {
        initial_pozition.x=initial_pozition.needed_key/m;
        initial_pozition.y=m;
    }
    else
    {
        initial_pozition.x=initial_pozition.needed_key/m+1;
        initial_pozition.y=initial_pozition.needed_key-(initial_pozition.x-1)*m;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j].val);

            v[a[i][j].val].push_back((i-1)*m+j);
        }
        i+=0;
    }
}
int di[]={0,1,0,-1,0};
int dj[]={0,0,1,0,-1};
bool neighbours(int val)
{
    int coord_x,coord_y;
    coord_x=val/m+1;
    coord_y=val-(coord_x-1)*m;

    if(val%m==0)
    {
        coord_x--;
        coord_y=m;
    }
    if(coord_x<=0||coord_y<=0)
        return false;
    if(coord_x>n||coord_y>m)
        return false;
    if(a[coord_x][coord_y].vizited[0]==1)
        return false;
    int directions;
    for(directions=1;directions<=4;directions++)
    {
        if(a[coord_x+di[directions]][coord_y+dj[directions]].vizited[0]==1)
        {
            a[coord_x][coord_y].vizited.set();
            solution++;
            return true;
        }

    }
    return false;
}
bool no_options()
{
    int i,j;
    bool da=true;
    for(i=1;i<=curent_keys[0];i++)
    {
        for(j=1;j<=v[curent_keys[i]].size();j++)
        {

            if(neighbours(v[curent_keys[i]][j-1])==true)
            {
                curent_keys[++curent_keys[0]]=v[curent_keys[i]][j-1];
                da=false;
            }
        }
    }
    return da;
}
int main()
{
    freopen("castel.in","r",stdin);
    freopen("castel.out","w",stdout);
    read();
    a[initial_pozition.x][initial_pozition.y].vizited.set();
    solution++;
    curent_keys[++curent_keys[0]]=initial_pozition.needed_key;
    while(!no_options())
    {

    }
    printf("%d",solution);
    return 0;
}