824 Insule

[•superman_01]

am facut cum zici...si tot iau TLE pe alea 2 si nu inteleg de ce ....

[•cosminionut]

Podul nu poate fi in zigzag , nu ?

[•GoldEagle]

Chiar nu-mi dau seama unde cicleaza codul.  Poate va uitati putin si ma ajutati si pe mine

#include<iostream>
#include<fstream>
using namespace std;

ifstream f ("insule.in");
ofstream gin ("insule.out");

int a[100][100],i,j,n,m,b[100][100];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};

struct punct {int x,y;} c[10000];

void fill (int x,int y,int k)
{if (a

• [y]==k) {a
• [y]=k*-1;

fill(x-1,y,k);
fill(x,y+1,k);
fill(x+1,y,k);
fill(x,y-1,k);}}

int lee(int x0,int y0)
{int k,u,p,xc,yc,xv,yv;
   for (i=0;i<=n+1;i++)
   for (j=0;j<=m+1;j++)
      b[j]=a[j];
c[1].x=x0; c[1].y=y0;
u=p=1;
while (p<=u)
{xc=c[p].x; yc=c[p].y;
   for (k=0;k<4;k++)
{xv=xc+dx[k];
yv=yc+dy[k];
if (b[xv][yv] == -2) return b[xc][yc];
else
   if (b[xv][yv] == 0)
   {b[xv][yv]=b[xc][yc]+1;
   u++; c.x=xv;  c.y=yv;}
else
   if (b[xv][yv]>0 && b[xv][yv]>b[xc][yc]+1)
   {b[xv][yv]=b[xc][yc]+1;
   u++; c.x=xv; c.y=yv;}
} }
p++;}

int main()
{   char x;
int q,min=10000;
   int r=0,g=0,b=0;
    f>>n>>m;
//bordare matrice cu -4;
for (i=0;i<=n+1;i++)
   a

• =a[m+1]=-4;

for (j=0;j<=m+1;j++)
   a[0][j]=a[n+1][j]=-4;
//citire in matrice;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{f>>x; a[j]=x-'0';}
//verificare numar insule;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{if (a[j]==1) {r++; fill(i,j,1);}
if (a[j]==2) {g++; fill(i,j,2);}
if (a[j]==3) {b++; fill(i,j,3);}}
//lungime min pod;
for (i=1;i<=n;i++)
   for (j=1;j<=m;j++)
   {q=lee(i,j);
   if (q<min) min=q;}

gin<<r<<" "<<g<<" "<<b<<" "<<min;
f.close(); gin.close();
return 0;}

[•pop_bogdan]

nu inteleg, imi da exact ca in exemplu si iau 0,rezolvarea cred ca este buna ...am trimis si pe evaluatorul de pe campion.edu.ro,si acolo la exemplu 0 puncte,chiar daca imi da exact la fel. Uitati-va va rog peste cod si spuneti-mi ce sa fac:

#include <cstdio>
#define MAX 101
using namespace std;

int x[MAX][MAX], a[MAX][MAX];
int n,m,size,max(-9999),R,G,B;
int d1[] = { -1, 0, 1, 0};
int d2[] = { 0, 1, 0, -1 };
int minim(999999);

bool ok(int i, int j)
{
    if ( a[j] != 0 )
    return false;
    if ( i < 1 || j < 1 || i > m || j > m)
    return false;
    return true;
}

void lee()
{
    int k(4); int v1,v2;bool modif = true;
    while ( modif )
    {
        modif = false;
    for ( int i = 1; i <= n; i++)
        for ( int j = 1; j <= m; j++ )
        if ( a[j] == k)
        {
            for ( int d = 0; d < 4; d++ )
            {
                v1 = i + d1[d];
                v2 = j + d2[d];
                if ( ok(v1,v2) )
                {
                a[v1][v2] = k+1;
                modif = true;
                }
            }

        }
         k++;
    }
}

struct pozitie{
    int linie;
    int coloana;
    };

void fill(int i,int j,int k)
{
    if ( x[j] == 1)
    {
        x[j]=k;
        size++;
        if ( x[i-1][j] == 1) fill(i-1,j,k);
        if ( x[i+1][j] == 1) fill(i+1,j,k);
        if ( x[j-1] == 1) fill(i,j-1,k);
        if ( x[j+1] == 1) fill(i,j+1,k);

    }
    if ( x[j] == 2)
    {
        x[j]=k;
        size++;
        if ( x[i-1][j] == 2) fill(i-1,j,k);
        if ( x[i+1][j] == 2) fill(i+1,j,k);
        if ( x[j-1] == 2) fill(i,j-1,k);
        if ( x[j+1] == 2) fill(i,j+1,k);

    }
    if ( x[j] == 3)
    {
        x[j]=k;
        size++;
        if ( x[i-1][j] == 3) fill(i-1,j,k);
        if ( x[i+1][j] == 3) fill(i+1,j,k);
        if ( x[j-1] == 3) fill(i,j-1,k);
        if ( x[j+1] == 3) fill(i,j+1,k);

    }
}



int main()
{
    char c;int d;
    pozitie p1[100];
    pozitie p2[100];
    FILE * pFile;
    pFile = fopen("insule.in", "r");
    fscanf(pFile,"%d%d\n", &n,&m);
    for ( int i = 1; i <= n ; i++ )
    {
        for ( int j = 1 ; j <= m; j++ )
        {
            fscanf(pFile,"%c",&c);
            x[j] = c - '0';
            a[j] = c - '0';
        }
        fprintf(pFile,"\n");
    }
    int k = 3;
    for ( int i = 1; i <= n; i++ )
        for ( int j = 1; j <= m; j++ )
        if ( x[j] == 1 || x[j] == 2 || x[j] == 3 )
        {
            k++;
            if ( x[j] == 1)
            R++;
            if ( x[j] == 2)
            G++;
            if ( x[j] == 3)
            B++;
            size = 0;
            fill(i,j,k );
            if ( size > max )
            max = size;
        }
        int o = 0;
        int p = 0;
        int j1,j2;
    for ( int i = 1; i <= n; i++ )
        for ( int j = 1; j <= m; j++ )
        {
            if ( a[j] == 0 )
            {
                if ( a[i-1][j] == 1 || a[i+1][j] == 1 || a[j-1] == 1 || a[j+1] == 1)
                {
                    p1

• .linie = i;

                    p1

• .coloana = j;

                    j1 = i;
                    j2 = j;
                    a[j1][j2] = 4;
                    o++;
                }
                if ( a[i-1][j] == 2 || a[i+1][j] == 2 || a[j-1] == 2 || a[j+1] == 2)
                {
                    p2[p].linie = i;
                    p2[p].coloana = j;
                    p++;
                }
            }
        }
    lee();
    int f,g;
    for ( int j = 0; j < p ; j++ )
        {
            f = p2[j].linie;
            g = p2[j].coloana;
            if ( a[f][g] < minim && a[f][g] != 0)
            minim = a[f][g];
        }
    minim -= 3;
    pFile = fopen("insule.out", "w");
    fprintf(pFile, "%i %i %i %i" ,R,G,B,minim);

    return 0;
}

[•PlayLikeNeverB4]

Cod:

fprintf(pFile,"\n");

?

[•pop_bogdan]

Fara acea linie nu citeste matricea cum trebuie.daca nu o puneam,ramanea la prima linie citirea elementelor din matrice.

[•PlayLikeNeverB4]

Pune

Cod:

fscanf(pFile,"\n");

Ce sens are sa scrii intr-un fisier din care citesti?

[•Liviu98]

Va rog frumos sa ma ajutati!
Nu imi dau seama cum sa adaug toate zonele vecine in coada.Eu le-am luat pe toate si am facut Lee-ul la fiecare-n parte.Iau doar 70 de puncte.
Pe ultimele 3 teste iau TLE.
Ma incurc mereu.Are cineva o idee cum sa implementez?

[•Djok]

Daca te referi la aflarea numarului de insule, poti sa folosesti Flood fill http://en.m.wikipedia.org/wiki/Flood_fill

[•Liviu98]

Aflarea numarului de insule a fost simpla...punctul 2 ma intereseaza.Am facut lee-ul pt fiecare vecin al primei tari si iau 70 de puncte(ultimele 3 TLE).Eu vreau sa adaug toti vecinii in coada si sa fac o singura data lee-ul.Dar nu imi dau seama cum... 

[•Liviu98]

Aflarea numarului de insule a fost simpla...punctul 2 ma intereseaza.Am facut lee-ul pt fiecare vecin al primei tari si iau 70 de puncte(ultimele 3 TLE).Eu vreau sa adaug toti vecinii in coada si sa fac o singura data lee-ul.Dar nu imi dau seama cum...  

[•PlayLikeNeverB4]

Faci exact cum ai spus. Bagi totul in coada, setezi distanta pentru acele puncte la 0 si ii dai drumul. Nu e nimic special. Explica ce nu intelegi.

[•DragulinSilviu]

buna
nu stiu cum sa citesc matricea aia fara spati intre elemente   
ma poate ajuta cineva ?

[•PlayLikeNeverB4]

Citesti N siruri de caractere.

[•DragulinSilviu]

am facut problema ,am citit pe o matrice de tip char apoi am am trecut toate datele pe o matrice normala,pe datele de pe problema
imi da 4 2 3 4;dar cand am trimis problema am luat 0 puncte  ,de ce? te poti uita putin peste programul meu ? multumesc  anticipat !

#include <fstream>
#include <iomanip>
using namespace std;
ifstream x("insule.in");
ofstream y("insule.out");
struct lee
 {
     int lin,col;
 };
int dl[]={-1,0,1,0};//deplasarea pe linie
int dc[]={0,1,0,-1};//deplasarea pe coloana

char a[101][101];/*arhipelagul  cu insule,este de tip char
pt ca datele din matrice pe linie nu sunt separate prin spatiu*/

int i,j,m,n,prim,ultim,k,b[101][101],insule[4],limita;/*am facut
o copiiea arhipelaguluide tip int pentru ca pe char
nu pot prelucra datele,iar limitele le voi folosi in mai jos
in conditia de continuitate a algoritmului lui lee */

int pod,pod_min; // un pod si podul de lungime minima

lee c[10000],v,p,start; //coada,vecinul,pozitia curenta si startul


void citesc()
 {
     x>>n>>m;
     for(i=1;i<=n;i++)
       for(j=1;j<=m;j++)
         {
             x>>a[j];
             b[j]=a[j]-48;
         }

 }
void scriu()
 {

     for(i=1;i<=n;i++)
      {
           for(j=1;j<=m;j++)
             y<<setw(4)<<b[j];
           y<<'\n';

      }
     y<<"\n\n\n";
 }
void lee()
 {
     prim=ultim=0;
     c[0]=start;
     while(prim<=ultim)
      {
          p=c[prim];
          prim++;
          for(k=0;k<4;k++)
           {
               v.lin=p.lin+dl[k];
               v.col=p.col+dc[k];
               //if(b[v.lin][v.col]!=0 && b[v.lin][v.col]<100 )
               if(b[v.lin][v.col]==limita )
                {
                    b[v.lin][v.col]=b[v.lin][v.col]+100;
                    ultim++;
                    c[ultim]=v;

                }

           }

      }

 }
void p1()
 {
     for(i=1;i<=n;i++)
      for(j=1;j<=m;j++)
         {
             if(b[j]!=0 && b[j]<100)
               {
                   insule[b[j]]++;
                   start.lin=i;
                   start.col=j;
                   limita=b[j];
                   //y<<limita<<' ';
                   b[j]=b[j]+100;
                   lee();
               }
         }

 }
void lee2()/*am modificat potin lee-ul astfel incat de la start sa
sa ia directiile pe rand si la fiecare directie sa mearga in liniie
dreapnta pana cand gaseste sau nu gaseste ceva pt a fi numit pod;
daca incepe din 1 apoi parcrurgem numai zero-uri pana la un 2,il
consideram pod,daca il  consideram pod ne interesam daca este de
lungime minima...   */

 {
     prim=ultim=0;
     c[0]=start;
     for(k=0;k<4;k++)
      {
          v.lin=start.lin+dl[k];
          v.col=start.col+dc[k];
          while(a[v.lin][v.col]==0)
           {
               pod++;
               v.lin+=dl[k];
               v.col+=dc[k];
           }
          if(a[v.lin][v.col]==2 && pod<pod_min)
             pod_min=pod;
           pod=0;
      }

 }
void p2()
 {
     for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
       {
           if(a[j]==1)
            {
                start.lin=i;
                start.col=j;
                lee2();
            }

       }
      y<<pod_min;
 }

int main()
{
    citesc();
    //scriu();
    p1();
    //scriu();
    for(i=1;i<=3;i++) y<<insule<<" ";
    if(m<n) pod_min=m-2;//vad care ar putea fi lungimea maxima a unui pod
        else pod_min=n-2;
    p2();


    return 0;
}

[•VladTiberiu]

Imi explica si mie cineva de ce scrie N,M <= 100 si solutia mea ia 10 puncte pt a[102][102] , 88 puncte pe a[150][150], 70 puncte pe a[300][300] si 100 pentru a[256][256] ? Si nu cumva o matrice de 256 pe 256 si o coada (cu 2 unsigned char-uri) depaseste 640 kbytes?

[•blackodd]

BAD POST.
L.E:
Cei care credeti ca algoritmul este corect dar totusi nu luati 100, declarati matricea mai mare.
Pentru 3 matrici 101x101 am luat 88p, iar pentru 3 matrici 110x110 am luat 100p.

[•tiby10]

Am si eu o problema daca ma puteti ajuta:
sursa mea ia pe 9 teste 4 puncte cu eroarea "lungime minima gresita", un test fiind "OK" (total 46p ): http://www.infoarena.ro/job_detail/1462033?action=view-source

( am incercat sa iau si minimul de lungime a unui pod din subprogramul " podu'() ", ce face defapt si actualul subprogram din sursa de mai sus dar asa, ca chestie:
http://www.infoarena.ro/job_detail/1462036?action=view-source  si desigur, la fel: 46p ).

Nu pot sa mi dau seama unde ar fi problema, in principiu ar trebui sa fie bine, si pe actualul exemplu imi da bine.

[•alinp25]

Pe 8/10 teste imi da "Lungimea minima gresita"... Putin ajutor se poate?

Cod:

#include <iostream>
#include <fstream>
#include <queue>
 
std::ifstream fin("insule.in");
std::ofstream fout("insule.out");
 
int n, m; //Linii, coloane
int Map[105][105]; //Matrice
std::queue < std::pair < int, int > > coada; //Coada
std::queue < std::pair < int, int > > pod; //CoadaPentruPod
const int di[4] = {1, -1, 0, 0}, //Deplasare pe linie
          dj[4] = {0, 0, 1, -1}; //Deplasare pe coloana
int tipInsula;
int insule[4], Lg = 999999;
 
void Read(){
    char c;
    fin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            fin >> c;
            Map[i][j] = c - '0';
        }
    }
}
 
bool OKinsula(int a, int b, int t){
    if(Map[a][b] == t && a >= 1 && b >= 1 && a <= n && b <= m)
        return true;
    return false;
}
 
bool OKapa(int a, int b){
    if(Map[a][b] == 0 && a >= 1 && b >= 1 && a <= n && b <= m)
        return true;
    return false;
}
 
bool apaInceputPod(int a, int b){
    if (Map[a][b] == 0 && (Map[a-1][b] == 1 || Map[a+1][b] == 1 || Map[a][b-1] == 1 || Map[a][b+1] == 1 || Map[a-1][b] == -1 || Map[a+1][b] == -1 || Map[a][b-1] == -1 || Map[a][b+1] == -1))
        return true;
    return false;
}
 
void numarInsule(){
    int i_curent, j_curent; //Pastrarea pozitiei curente
    int i_urmator, j_urmator; //Pastrarea pozitiei urmatoare
    while (!coada.empty()){
        i_curent = coada.front().first;
        j_curent = coada.front().second;
        coada.pop();
        for (int directie = 0; directie < 4; directie++){
            i_urmator = i_curent + di[directie];
            j_urmator = j_curent + dj[directie];
            if (OKinsula(i_urmator, j_urmator, tipInsula)){
                coada.push(std::make_pair(i_urmator, j_urmator));
                Map[i_urmator][j_urmator] *= -1;
            }
        }
    }
}
 
void verificaLungimea(){
    for (int a = 1; a <= n; a++){
        for (int b = 1; b <= n; b++){
            if (Map[a][b] > 0 && (Map[a-1][b] == -2 || Map[a+1][b] == -2 || Map[a][b-1] == -2 || Map[a][b+1] == -2)){
                if(Map[a][b] <= Lg){
                    Lg = Map[a][b];
                }
            }
        }
    }
}
 
void calculeazaLungimea(){
    int i_curent, j_curent; //Pastrarea pozitiei curente
    int i_urmator, j_urmator; //Pastrarea pozitiei urmatoare
    i_curent = pod.front().first;
    j_curent = pod.front().second;
    Map[i_curent][j_curent] = 1;
    while (!pod.empty()){
        i_curent = pod.front().first;
        j_curent = pod.front().second;
        pod.pop();
        for (int directie = 0; directie < 4; directie++){
            i_urmator = i_curent + di[directie];
            j_urmator = j_curent + dj[directie];
            if (OKapa(i_urmator, j_urmator)){
                pod.push(std::make_pair(i_urmator, j_urmator));
                Map[i_urmator][j_urmator] = Map[i_curent][j_curent] + 1;
            }
        }
    }
    verificaLungimea();
}
 
int main(int argc, char *argv[]){
    Read();
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (apaInceputPod(i, j)){
                pod.push(std::make_pair(i, j));
            }else if (Map[i][j] > 0 && i >= 1 && j >= 1 && i <= n && j <= m){
                tipInsula = Map[i][j];
                switch (Map[i][j]){
                    case 1:
                        insule[1]++;
                        break;
                    case 2:
                        insule[2]++;
                        break;
                    case 3:
                        insule[3]++;
                        break;
                    default:
                        break;
                };
                if(coada.empty())
                    Map[i][j] *= -1;
                coada.push(std::make_pair(i, j));
                numarInsule();
            }
        }
    }
    calculeazaLungimea();
    fout << insule[1] << " " << insule[2] << " " << insule[3] << " " << Lg;
    return 0;
}

[•samoilescusebastian]

Buna seara !Am si eu o nedumerire,pentru exemplul urmator ce ar trebui sa afiseze programul?
6 7
1 0 0 0 3 2 0
0 1 1 0 3 1 3
3 3 3 0 0 0 2
2 0 3 3 0 0 0
2 2 0 3 0 1 1
2 0 0 0 0 1 0
Multumesc!

[•AlexandruValeanu]

Mie imi da:

Cod:

4 3 3 1

[•Nannyi]

Nu stie cineva de ce primesc constant 0 puncte?

Cod:

#include <iostream>
#include <fstream>
using namespace std;

ifstream f("insule.in");
ofstream g("insule.out");


int dl[4]= {0,1,0,-1};
int dc[4]= {1,0,-1,0};
int v[250][250];
int x[4];
void Lee(int i,int j,int &mx,int n,int m)
{

    for (int di=0; di<4; di++)
    {
        int iu=i,ju=j,o=0;
        iu+=dl[di];
        ju+=dc[di];
        while (v[iu][ju]==0&&iu>-1&&ju>-1&&iu<n&&ju<m)
        {
            o++;
            iu+=dl[di];
            ju+=dc[di];
        }
        if (v[iu][ju]==2)
            if (o<mx&&o!=0)
                mx=o;
    }
}


int main()
{
    int n,m,a,mx=105;
    f>>n>>m;
    for (int i=0; i<n; i++)
    {
        f>>a;
        int j=0;
        while (a)
        {
            v[i][m-j-1]=a%10;
            a/=10;
            j++;
        }
    }
    for (int i=0; i<n; i++)
        for (int j=0; j<m; j++)
        {
            if (v[i][j])
                if (v[i-1][j]!=v[i][j]&&v[i][j-1]!=v[i][j])
                    x[v[i][j]]++;
            if (v[i][j]==1)
                Lee(i,j,mx,n,m);
        }
    for (int i=1; i<4; i++)
        g<<x[i]<<' ';
    if (mx!=105)
    g<<mx;
    else
        g<<0;
    f.close();
    g.close();
    return 0;
}

[•nicolaefilat]

Nu esti corect, fraiere !!!