Cod sursa(job #2344807)

Utilizator YetoAdrian Tonica Yeto Data 15 februarie 2019 17:26:47
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("castel.in");
ofstream fout ("castel.out");
int n, m, k, i, j, i1, j1, st, dr, sol, ln, cn;
int a[152][152];
short int b[155][155];
bool chei[22505];
vector <int> ch[22505];
struct coada {
    short int l, c;
}q[100000];
int dx[] = {0, 1, 0, -1, 0};
int dy[] = {0, 0, 1, 0, -1};

int ord (int x, int y)
{
    return (x-1)*m+y;
}
void invord(int x, int &i1, int &j1)
{
    if (x%m==0) {
        i1=x/m, j1=m;
    }else {
        i1=x/m+1;
        j1=x%m;
    }
}

int main () {
    fin>>n>>m>>k;
    for (i=1;i<=n;i++) {
        for (j=1;j<=m;j++)
            fin>>a[i][j];
    }

    st=1;
    dr=1;
    invord(k, i1, j1);
    q[st].l=i1;
    q[st].c=j1;
    b[i1][j1]=2;
    sol++;
    ch[a[i1][j1]].push_back(ord(i1, j1));
    while (st<=dr) {
        int l=q[st].l;
        int c=q[st].c;
        int nr=ord(l,c);
        chei[nr]=1;
        for (i=0;i<ch[nr].size();i++) {
            invord(ch[nr][i], i1, j1);
            if (b[i1][j1]==1) {
                q[++dr].l=i1;
                q[dr].c=j1;
                b[i1][j1]=2;
                chei[ord(i1, j1)]=1;
                sol++;
            }
        }
        for (i=1;i<=4;i++) {
            int ln=l+dx[i];
            int cn=c+dy[i];
            if (ln>0 && ln<=n && cn>0 && cn<=m && b[ln][cn]!=2) {
                if (chei[a[ln][cn]]) {
                    q[++dr].l=ln;
                    q[dr].c=cn;
                    if (b[ln][cn]==0) {
                        ch[a[ln][cn]].push_back(ord(ln, cn));
                    }
                    b[ln][cn]=2;
                    chei[ord(ln, cn)]=1;
                    sol++;
                }
                else {
                    ch[a[ln][cn]].push_back(ord(ln, cn));
                    b[ln][cn]=1;
                }
            }

        }
        st++;
    }

    fout<<sol;
    return 0;
}