477 Alee

[•poptibi]

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

Avand in vedere ca evaluatorul nu mai functioneaza de la ora 12 (cred ca ai observat asta), tot ce poti face e sa astepti sa revina si apoi iti poti trimite si sursele.

PS: solutii*

[•otniel]

de ce i-au memory limit exced pe testele 6,7,8 cu solutia
#include<iostream>
#include<stdio.h>
FILE *f,*g;
using namespace std;
const int x2[4]={0,0,1,-1};
const int y2[4]={1,-1,0,0};
long long a[178][178],x1,y1,n,m,x0,y0,i,j,u,t,inceput=1,sfarsit=1;
struct punct
{
    int ls,ld,d;
};
punct coada[31684],x,y;
int main()
{
    f=fopen("alee.in","r");
    g=fopen("alee.out","w");
    fscanf(f,"%lld%lld",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%lld%lld",&u,&t);
        a[t]=-1;
    }
    fscanf(f,"%lld%lld%lld%lld",&x0,&y0,&x1,&y1);
    for(i=0;i<=n+1;i++)
    {
        a[0]=a[n+1]=-1;
        a

• =a[n+1]=-1;

    }
    coada[inceput].ls=x0;
    coada[inceput].ld=y0;
    coada[inceput].d=1;
    a[x0][y0]=1;
    while(inceput<=sfarsit)
    {
        x=coada[inceput];
        inceput++;
        for(int k=0;k<4;k++)
        {
            if(a[x.ls+x2[k]][x.ld+y2[k]]==0)
            {
                a[x.ls+x2[k]][x.ld+y2[k]]=x.d+1;
                y.d=x.d+1;
                y.ls=x.ls+x2[k];
                y.ld=x.ld+y2[k];
                sfarsit++;
                coada[sfarsit]=y;
                if(y.ls==x1&&y.ld==y1)
                {
                    fprintf(g,"%lld",a[y.ls][y.ld]);
                 break;
                }
            }
        }
    }
}

[•rares96cheseli]

de ce i-au memory limit exced pe testele 6,7,8 cu solutia
#include<iostream>
#include<stdio.h>
FILE *f,*g;
using namespace std;
const int x2[4]={0,0,1,-1};
const int y2[4]={1,-1,0,0};
long long a[178][178],x1,y1,n,m,x0,y0,i,j,u,t,inceput=1,sfarsit=1;
struct punct
{
    int ls,ld,d;
};
punct coada[31684],x,y;
int main()
{
    f=fopen("alee.in","r");
    g=fopen("alee.out","w");
    fscanf(f,"%lld%lld",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%lld%lld",&u,&t);
        a[t]=-1;
    }
    fscanf(f,"%lld%lld%lld%lld",&x0,&y0,&x1,&y1);
    for(i=0;i<=n+1;i++)
    {
        a[0]=a[n+1]=-1;
        a

• =a[n+1]=-1;

    }
    coada[inceput].ls=x0;
    coada[inceput].ld=y0;
    coada[inceput].d=1;
    a[x0][y0]=1;
    while(inceput<=sfarsit)
    {
        x=coada[inceput];
        inceput++;
        for(int k=0;k<4;k++)
        {
            if(a[x.ls+x2[k]][x.ld+y2[k]]==0)
            {
                a[x.ls+x2[k]][x.ld+y2[k]]=x.d+1;
                y.d=x.d+1;
                y.ls=x.ls+x2[k];
                y.ld=x.ld+y2[k];
                sfarsit++;
                coada[sfarsit]=y;
                if(y.ls==x1&&y.ld==y1)
                {
                    fprintf(g,"%lld",a[y.ls][y.ld]);
                 break;
                }
            }
        }
    }
}

pentru ca folosesti long long

[•otniel]

si cu int i-au tot memory limit exced

[•rares96cheseli]

si cu int i-au tot memory limit exced

in primul rand nu trebuie sa bordezi matricea. apoi ai de ales intre 2 optimizari:
1) pui short peste tot
2) schimbi citirea/scrierea. adica faci asa:

Cod:

freopen("alee.in","r", stdin);
freopen("alee.out","w", stdout);
scanf("%d%d",&n,&m);

[•otniel]

multumesc frumos

[•hopingsteam]

Imi poate spune cineva de ce primesc "Memory limit exceeded" pentru testele 6 si 8 ?

#Edit: Am fost smecher, si in struct am folosit unsigned char si dupa am convertit l = int(..); c = int(..); 

[•tudorgalatan]

Am utilizat metoda cu funcția queue din STL, dar îmi dă doar 60 de puncte la problemă. Am verificat fiecare test oficial de la OJI și îmi dă corect pe toate testele. Care ar putea fi problema?

[•Djok]

matricea declarată de tine este prea mică.
100x100 cînd N<=175

[•tudorgalatan]

Până la urmă mi-am dat seama că nu luasem în calcul acea restricție, dar mulțumesc frumos oricum!

[•Andrei2000]

Salut ! Imi poate spune cineva de ce iau Memory limit exceeded la testele 7 si 8 ?

Cod:

#include <fstream>

using namespace std;

ifstream in ("alee.in");
ofstream ou ("alee.out");

int v[177][177],n,m;

struct coord{
    int lin,col;
};

coord gate,q[180*180],p,w;

int vl[]={-1,0,1,0};
int vc[]={0,1,0,-1};

int prim=1,ultim=1;

int main()
{
    int a,b,i,j;
    in>>n>>m;
    for (i=1;i<=m;++i){
        in>>a>>b;
        v[a][b]=-1;
    }
    for (i=0;i<=n+1;++i){
        v[i][0]=v[i][n+1]=v[0][i]=v[n+1][i]=-1;
    }
    in>>gate.lin>>gate.col>>a>>b;
    q[1].lin=gate.lin;
    q[1].col=gate.col;
    v[gate.lin][gate.col]=1;
    while (prim<=ultim && v[a][b]==0){
        p.lin=q[prim].lin;
        p.col=q[prim].col;
        prim++;
        for (i=0;i<=3;++i){
            w.lin=p.lin+vl[i];
            w.col=p.col+vc[i];
            if (v[w.lin][w.col]==0){
                v[w.lin][w.col]=v[p.lin][p.col]+1;
                ultim++;
                q[ultim].lin=w.lin;
                q[ultim].col=w.col;
            }
        }
    }
    ou<<v[a][b]<<"\n";
    ou.close();
    return 0;
}

[•nacroc]

Incearca cu short in loc de int, restul pare ok

[•alexmercan2016]

error : stray \377

 

Cod:

#include<fstream>
#include<queue>


using namespace std;

ifstream fin("alee.in");
ofstream fout("alee.out");

int di[4] = { 0, 0,1, -1 };
int dj[4] = { 1, -1, 0, 0 };
int map[180][180];
int N, M, startx, starty, endx, endy;
queue<pair<int, int>> myQueue;

void read()
{
	int x, y;	
	fin >> N >> M;
	for(int i=0;i<M;i++)
	{
		fin >> x >> y;
		map[x][y] = -1;	
	}
	fin >> startx >> starty;
	fin >> endx >> endy;
}

bool ok(int i, int j)
{
	if (i<1 || j<1 || i>N || j>N)
		return false;
	if (map[i][j] == -1)
		return false;
	return true;
}

void Lee()
{
	int i, j, nexti, nextj;
	map[startx][starty] = 1;
	myQueue.push(make_pair(startx, starty));
	while (!myQueue.empty())
	{
		i = myQueue.front().first;
		j = myQueue.front().second;
		myQueue.pop();
		for(int dir=0;dir<=3;dir++)
		{
			nexti = i + di[dir];
			nextj = j + dj[dir];
			if (ok(nexti, nextj) && map[nexti][nextj] ==0)
			{
				map[nexti][nextj] = map[i][j] + 1;
				myQueue.push(make_pair(nexti, nextj));
			}
		}
	}
}

int main()
{
	read();
	Lee();
	fout << map[endx][endy];
    return 0;
}