Cod sursa(job #1266188)

Utilizator tudormaximTudor Maxim tudormaxim Data 18 noiembrie 2014 14:22:14
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <cstdio>
#define nmax 155
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
int m, n, k, xx, yy, nx, ny, sol=1;
bool key[nmax * nmax], used[nmax][nmax];
struct Matrice{int x; int y; }q[nmax*nmax], a[nmax][nmax];
bool okay(int i, int j)
{
    if (i < 1 || i > m || j < 1 || j > n) return 0;
    if (used[i][j] || !key[a[i][j].x]) return 0;
    return 1;
}
void Lee()
{
    int inc=1, sf=1;
    q[1].x=xx;
    q[1].y=yy;
    used[xx][yy]=1;
    key[k]=1;
    bool ok=1;
    while(ok)
    {
        for(inc=1, ok=0; inc<=sf; inc++)
        {
            int i=q[inc].x;
            int j=q[inc].y;
            for(int d=0; d<4; d++)
            {
                nx=i+dx[d];
                ny=j+dy[d];
                if (okay(nx, ny))
                {
                    sf++;
                    q[sf].x=nx;
                    q[sf].y=ny;
                    used[nx][ny]=1;
                    key[a[nx][ny].y]=1;
                    sol++;
                    ok=1;
                }
            }
        }
    }
}
int main()
{
    freopen("castel.in", "r", stdin);
    freopen("castel.out", "w", stdout);
    scanf("%d %d %d\n", &m, &n, &k);
    int nr=0;
    for (int i=1; i<=m; ++i)
    {
        for (int j=1; j<=n; ++j)
        {
            ++nr;
            scanf("%d", &a[i][j].x);
            a[i][j].y = nr;
            if (k==nr)
            {
               xx=i;
               yy=j;
            }
        }
    }
    Lee();
    printf("%d\n", sol);
    return 0;
}