477 Alee

[•flaviusc11]

Multumesc de raspuns. Voi incerca sa rezolv asa, dar nu acum.

[•ctlin04]

poate sa-mi sugereze cineva vreo optimizare pentru PD, am TLE la testul 7 si nu inteleg care ar fi problema pentru ca celelalte teste merg destul de bine

[•PlayLikeNeverB4]

Testul 7 e cel mai mare probabil pentru ca si la mine are cel mai mare timp.
Poate e de la citire. Incearca sa introduci asta:

Cod:

var bufin:array[1..50000] of byte;
..........
Assign(f,'alee.in'); Reset(f);
settextbuf(f,bufin);

P.S.: Treci la C, Pascal sux.

[•ctlin04]

Las ca-i bun si pascalu, am abordat problema altfel si am scos cu pascalul 12ms, iar daca faceam in c sau cpp si mergea sursa pe 100 puncte cu ideea ineficienta atunci credem ca-i buna ideea, dar in timp de concurs puteam  s-o dau in bara dar asa am avut un stimul pentru a ma gindi la alta metoda de rezolvare.

[•vendetta]

crezi tu ca te va ajuta pascal-ul; si eu pana acum 1 luna jumate foloseam pascal-ul, desi stiam c++ teoria, doar ca imi era foarte greu sa ma "las" de pascal;daca citeam o problema si vroiam sa o rezolv o faceam in pascal desi mi`am propus sa o rezolv in c++... te inteleg daca iti e greu sa te lasi de pascal...dar iti spun din propria experienta ca MERITA... daca o sa devi programator baza tuturor limbajelor va fi c++/c si tie iti va fi mai usor sa intelegi acel program fata de ceilalti care nu sunt familiarizati cu c++...c++ contine si libraria STL(pe care o inveti din mers) iti face implementarea MULT MAI USOARA!
unul din motivele pt care m`am lasat de pascal a fost din cauza listelor,la grafuri la maj. problemelor graful il retii in liste si era mult de implementat si "urata" sursa...asa ca am trecut pe c++...deci la inceput in c++ faceam greseli de implementare(si acum mai fac) gen la cititre uitam "&" si imi pierdeam 10 minute(sau mai mult ) pana sa observ ca acolo era greseala... oricum sfatul meu e sa te apuci c++!

[•SpiderMan]

E bun si Pascalul pana la un moment dat, cand realizezi ca, cu C-ul poti mai mult. Incearca incet incet sa citesti si C, si orice program facut in Pascal sa reusesti sa-l transcrii in C. Apoi, incetul cu incetul sa faci programul direct in C, si sa lasi de tot Pascalul, pentru ca in viitor, daca te specializezi pe programare, o sa lucrezi cel mai probabil Java, sau C, care sunt foarte inrudite. Sfatul meu, tu oricum faci ce vrei, doar ca o sa-ti ajute mult de tot.

[•ctlin04]

Ms pentru sfaturi, cel mai probabil ca le voi urma 

[•Mitza444]

Buna am incercat sa rezolv si eu problema cu un Lee ,dar nu stiu din ce cauza imi da doar 90p...
Am incercat 2 variante una in care parcurgeam toata matricea ca sa aflu pasul de dinainte si dupaia marcam toti vecini cu pasul de dinainte +1 si asa imi pica la cel mai mare test la timp de executie,iar cand am facut cu o coada in care am retinut punctele imi pica la alt test,tot la timpu de executie 
Aici e rezolvarea cu coada:

Cod:

#include<cstdio>
using namespace std;
#define Nmax 175
int mat[Nmax][Nmax],c[Nmax*Nmax][3],N,M,x,y,x1,y1,x2,y2,p,u,xnou,ynou,d,i,j,m;
const int di[] = { -1, 0, 1, 0 },dj[] = { 0, 1, 0, -1 };
bool OK(int k,int q){
	if(mat[k][q]!=0){return false;}
	if(k<1 || q<1 || k>N || q>N){
		return false;}
	return true;
}
void Lee(){
	c[1][1]=x1;c[1][2]=y1;
	for(p=1,u=1;p<=u;p++){
		m=u;
		for(j=p;j<=m;j++){
		x=c[j][1];
		y=c[j][2];
		for(d=0;d<4;d++){
			xnou=x+di[d];
			ynou=y+dj[d];
			if(OK(xnou,ynou)){
				mat[xnou][ynou]=p+1;
				c[++u][1]=xnou;
				c[u][2]=ynou;
				if(xnou==x2 && ynou==y2){
					return;
				}
			}
		}
		}
	}
}
int main(){
	FILE * pFile;
	pFile=fopen("alee.in","r");
	fscanf(pFile,"%d%d",&N,&M);
	for(i=1;i<=M;i++){
		fscanf(pFile,"%d%d",&x,&y);
		mat[x][y]=-1;
	}
	fscanf(pFile,"%d%d%d%d",&x1,&y1,&x2,&y2);
	mat[x1][y1]=1;
	Lee();
	pFile=fopen("alee.out","w");
	fprintf(pFile,"%d",mat[x2][y2]);
	return 0;
}

[•SpiderMan]

Din cate vad eu nu ai folosit matrice de vizitati, adica sa nu mergi de 2 ori prin acelasi loc. Daca ai face o matrice gen viz[k][q] = 1 daca ai trecut prin pozitia k, q si 0 altfel. Initializezi viz[x1][y1] = 1, si faci lee-ul, iar la functia OK adaugi urmatoarea conditie : daca viz[k][q] = true atunci returneaza fals, si automat cand bagi in coada noul element, vad la tine xnou, ynou, faci asa : viz[xnou][ynou] = 1. Ar trebui sa iei 100 fara mari probleme.

[•Magnus]

@robert: daca te uiti mai bine, o sa vezi ca mihai foloseste mat ca matrice de vizitati
@mihai: fa asa functia lee ca e ceva mai rapid si mai simplu

Cod:

void Lee(){
	c[1][1]=x1;c[1][2]=y1;
	for(p=1,u=1;p<=u;p++){
		x=c[p][1];
		y=c[p][2];
		for(d=0;d<4;d++){
			xnou=x+di[d];
			ynou=y+dj[d];
			if(OK(xnou,ynou)){
				mat[xnou][ynou]=mat[x][y]+1;
				c[++u][1]=xnou;
				c[u][2]=ynou;
				if(xnou==x2 && ynou==y2){
					return;
				}
			}
		}
	}
}

si inca ceva: defineste Nmax ca fiind 176 pt ca atunci cand definesti un vector de x elemente tu definesti elementele de la 0 la x-1

[•SpiderMan]

DA am vazut, dar apare problema (nu stiu daca la el) cand elementul mat poate fi 0, si de fapt el a fost vizitat. In fine oricum, reuseste el .

[•Magnus]

mat[x1][y1] este initializat cu 1, eu nu vad unde poate aparea 0

[•PlayLikeNeverB4]

Problema este ca desi tu verifici toate elementele din coada de la p la u, incrementezi p doar cu 1.
Schimba for(p=1,u=1;p<=u;p++)   cu   for(p=1,u=1;p<=u;p=m+1)
si  ( ce au scris si cei de mai sus - Copyright Daniel Anghel © )

Dupa ce faci astea, o sa iti intre in timp dar o sa ai MLE.

Dar iti intra in memorie daca declari c[Nmax*Nmax][2] si retii cele doua coordonate ca si c[ ][0] si c[ ][1].

[•Magnus]

de fapt ar trebui sa-i intre in memorie si asa:

Cod:

((176*176*4+20)*32)/(1024*8)=484<640

 

[•PlayLikeNeverB4]

Teoretic, da. Nu stiu exact cum functioneaza evaluatorul, insa cred ca mai are nevoie de memorie pentru alte lucruri.

[•Magnus]

da, corect
ia mle 

[•Mitza444]

Mda, merge cum a zis Daniel doar ca a trebuit sa le declar toate short ca sa treaca si la memorie 

[•VisuianMihai]

stie cineva unde gresesc? iau 40 puncte:

Cod:

int lee ( int n, int a[176][176], int x2, int y2 )
{
	int gasit, k, i, j, inou, jnou, d;
	k = 0;
	do
	{
		gasit = 0;
		for ( i = 1; i <= n; i++ )
			for ( j = 1; j <= n; j++ )
			{
				if ( a[i][j] == k )
				{
					for ( d = 0; d <= 3; d++ )
					{
						inou = i + di[d];
						jnou = j + dj[d];
						if ( a[inou][jnou] == -1 || a[i][j] < a[inou][jnou]-1)
							a[inou][jnou] = k+1;
						if ( inou == x2 && jnou == y2 )
						{
							return a[inou][jnou]+1;
						}
					}
					gasit = 1;
				}
			}
			k++;
	}
	while ( gasit );
	return 0;
}

[•soriyn]

Pentru lee ai nevoie de o coada in care sa bagi nodurile accesibile la un moment dat. Nu prea cred ca merge cum vrei tu sa faci. Ce faci cu acel k ? Vezi ca nu mereu pleci din punctul de coordonate (1,1)

[•VisuianMihai]

Pentru lee ai nevoie de o coada in care sa bagi nodurile accesibile la un moment dat. Nu prea cred ca merge cum vrei tu sa faci. Ce faci cu acel k ? Vezi ca nu mereu pleci din punctul de coordonate (1,1)

k e numarul de pasi la un moment dat si il incrementez dupa fiecare parcurgere.

Later Edit: AM luat suta ... Din greseala am declarat vectorii cu coordonatele pomilor prea mici: numai de o suta

[•Eby7]

Problema mi-a iesit de 90 de puncte...imi da un Memory Limit exceended la testul 8...aveti idee de ce??
PS: am rezolvat prin lee clasic

[•CosminRusu]

Sursa mea ia 60 de puncte . MLE pe testul 8 si pe restul pe care nu le-a trecut Incorect. 
Nu inteleg, am tratat cazul particular cand raspunsul e 0 si tot aceeasi treaba. Multumesc anticipat  .

Cod:

#include <fstream>
using namespace std;
ifstream cin("alee.in");
ofstream cout("alee.out");
int n, m, l[180][180], q[4][31625], i,j , starti, startj, endi, endj, u, p;
void init()
{
    int x, y;
    cin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            l[i][j]=-2;
    for(i=1;i<=m;++i)
        {
            cin>>x>>y;
            l[x][y]=-1;
        }
    cin>>starti>>startj;
    l[starti][startj]=1;
    cin>>endi>>endj;
    l[endi][endj]=-3;
    q[1][1]=starti;
    q[2][1]=startj;
}
void intr(int c, int d)
{
    u=u+1;
    q[1][u]=c;
    q[2][u]=d;
}
void extr(int &c, int &d)
{
    p=p+1;
    c=q[1][p];
    d=q[2][p];
}
void lee()
{
    int x, y;
    u=1;
    p=0;
    while(p!=u)
    {
        extr(x,y);
        if(x>1)
                if(l[x-1][y]>l[x][y]+1 || l[x-1][y]==-2 || l[x][y+1]==-3)
                    {
                        l[x-1][y]=l[x][y]+1;
                        intr(x-1, y);
                    }
        if(y>1)
                if(l[x][y-1]>l[x][y]+1 || l[x][y-1]==-2 || l[x][y+1]==-3)
                    {
                        l[x][y-1]=l[x][y]+1;
                        intr(x, y-1);
                    }
        if(y<n)
                if(l[x][y+1]>l[x][y]+1 || l[x][y+1]==-2|| l[x][y+1]==-3)
                    {
                        l[x][y+1]=l[x][y]+1;
                        intr(x, y+1);
                    }
        if(x<n)
                if(l[x+1][y]>l[x][y]+1 || l[x+1][y]==-2|| l[x+1][y]==-3)
                    {
                        l[x+1][y]=l[x][y]+1;
                        intr(x+1, y);
                    }
    }
}
void afisare()
{
  //  for(i=1;i<=n;i++)
  //  {
  //      for(j=1;j<=n;j++)
  //          cout<<l[i][j]<<" ";
  //      cout<<"\n";
  //  }
    if(l[endi][endj]==-3)
        cout<<"0\n";
    else
    cout<<l[endi][endj]<<"\n";
}
int main()
{
    init();
    lee();
    afisare();
    return 0;
}

[•otniel]

dc nu raspunde evaluatorul?

[•rares96cheseli]

dc nu raspunde evaluatorul?

S-a suparat

[•otniel]

serios acuma ca nu mai pot trimite nici la alte probleme soluti pana nu mi-o ia pe aceasta