infoarena

   1. {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+}  
   2. {$M 16384,0,655360}  
   3. program lee;  
   4. const oriz:array[1..4]of shortint=(1,-1,0,0);  
   5.       vert:array[1..4]of shortint=(0,0,1,-1);  
   6. var f,g:text;  
   7.     v:array[1..175,1..175]of integer;  
   8.     modif:boolean;  
   9.     x,y,x1,y1,x2,y2,n:byte;  
  10.     m,pas,xnou,ynou,i:integer;  
  11. begin  
  12. assign(f,'alee.in');  
  13. assign(g,'alee.out');  
  14. reset(f);  
  15. rewrite(g);  
  16. readln(f,n,m);  
  17. for i:=1 to m do begin  
  18.     readln(f,x,y);  
  19.     v[x,y]:=-1;  
  20. end;  
  21. readln(f,x1,y1,x2,y2);  
  22. x:=1;y:=1;  
  23. modif:=true;  
  24. pas:=1;  
  25. v[x1,y1]:=pas;  
  26. while modif do begin  
  27.       modif:=false;  
  28.       for x:=1 to n do  
  29.           for y:=1 to n do  
  30.               if v[x,y]=pas then begin  
  31.                  for i:=1 to 4 do begin  
  32.                      xnou:=x+oriz[i];  
  33.                      ynou:=y+vert[i];  
  34.                      if (xnou in [1..n])and(ynou in [1..n]) then  
  35.                         if (v[xnou,ynou]=0)and(v[xnou,ynou]<>-1)then begin  
  36.                            v[xnou,ynou]:=pas+1;  
  37.                            modif:=true;  
  38.                         end;  
  39.                         if v[x2,y2]<>0 then begin  
  40.                            modif:=false;  
  41.                            x:=n;y:=n;  
  42.                         end;  
  43.                  end;  
  44.               end;  
  45.      pas:=pas+1;  
  46. end;  
  47. writeln(g,v[x2,y2]);  
  48. close(f);close(g);  
  49. end.  

#include<iostream.h>
#include<fstream.h>

int main()
	{
	struct orice
		{unsigned char x,y;}coada[31000];
	int parc[177][177],n,m,i,j,l,c,l2,c2,nr=0;
	fstream f("alee.in",ios::in),g("alee.out",ios::out);
	f>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			parc[i][j]=30625;
	for(i=1;i<=n;i++)
		{
		parc[0][i]=-1;parc[n+1][i]=-1;
		parc[i][n+1]=-1;parc[i][0]=-1;
		}
	for(i=1;i<=m;i++)
		{f>>l>>c;parc[l][c]=-1;}
	f>>l>>c>>l2>>c2;
	i=0;parc[l][c]=0;coada[0].x=l;coada[0].y=c;
	while(i<=nr)
		{
		l=int(coada[i].x);c=int(coada[i].y);
		if(parc[l][c]+1<parc[l+1][c])
			{parc[l+1][c]=parc[l][c]+1;nr++;coada[nr].x=l+1;coada[nr].y=c;}
		if(parc[l][c]+1<parc[l-1][c])
			{parc[l-1][c]=parc[l][c]+1;nr++;coada[nr].x=l-1;coada[nr].y=c;}
		if(parc[l][c]+1<parc[l][c+1])
			{parc[l][c+1]=parc[l][c]+1;nr++;coada[nr].x=l;coada[nr].y=c+1;}
		if(parc[l][c]+1<parc[l][c-1])
			{parc[l][c-1]=parc[l][c]+1;nr++;coada[nr].x=l;coada[nr].y=c-1;}
		i++;
		}
	g<<parc[l2][c2]+1;
	f.close();g.close();return 0;
	}

#include<iostream.h>
#include<fstream.h>

struct orice
		{unsigned char x,y;}coada[31000];


int main()
	{
	int n,m,i,j,l,c,l2,c2,nr=0,parc[177][177];
	fstream f("alee.in",ios::in),g("alee.out",ios::out);
	f>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			parc[i][j]=30625;
	for(i=1;i<=n;i++)
		{
		parc[0][i]=-1;parc[n+1][i]=-1;
		parc[i][n+1]=-1;parc[i][0]=-1;
		}
	for(i=1;i<=m;i++)
		{f>>l>>c;parc[l][c]=-1;}
	f>>l>>c>>l2>>c2;
	i=0;parc[l][c]=0;coada[0].x=l;coada[0].y=c;
	while(i<=nr)
		{
		l=int(coada[i].x);c=int(coada[i].y);
		if(parc[l][c]+1<parc[l+1][c])
			{parc[l+1][c]=parc[l][c]+1;nr++;coada[nr].x=l+1;coada[nr].y=c;}
		if(parc[l][c]+1<parc[l-1][c])
			{parc[l-1][c]=parc[l][c]+1;nr++;coada[nr].x=l-1;coada[nr].y=c;}
		if(parc[l][c]+1<parc[l][c+1])
			{parc[l][c+1]=parc[l][c]+1;nr++;coada[nr].x=l;coada[nr].y=c+1;}
		if(parc[l][c]+1<parc[l][c-1])
			{parc[l][c-1]=parc[l][c]+1;nr++;coada[nr].x=l;coada[nr].y=c-1;}
		i++;
		}
	g<<parc[l2][c2]+1;
	f.close();g.close();return 0;
	}

0 0 -1 0 0
0 -1 0 -1 0
0 0 -1 0 0
0 0 0 0 0
0 0 0 0 0

5 4
1 3
2 2
2 4
3 3
2 3 5 5

a[i][j]==x si a[i+1][j]==0 atunci in a[i+1][j] pun x+1

 a[x_finish][y_finish] 

int dirx[4] = {-1, 0, 1, 0};
int diry[4] = {0, -1, 0, 1};

...

for (int i = 1; i <= lungime_coada; ++i) {
  ...
  for (int j = 0; j < 4; ++j) {
     int x = coada_x[i] + dirx[j];
     int y = coada_y[i] + diry[j];
     // verificari pentru x si y si eventual adaugarea pozitiei in coada 
  }
  ...
}

#include<cstdio>
using namespace std;
int lb[175][175],n;
void drum(int k, int l, int c)
{
 if(l+1<n)
if(lb[l+1][c]>k+1)
  { lb[l+1][c]=k+1;
    drum(k+1,l+1,c); }
if(l>0)
if(lb[l-1][c]>k+1)
  { lb[l-1][c]=k+1;
    drum(k+1,l-1,c); }
if(c+1<n)
if(lb[l][c+1]>k+1)
  { lb[l][c+1]=k+1;
    drum(k+1,l,c+1); }
if(c>0)
if(lb[l][c-1]>k+1)
  { lb[l][c-1]=k+1;
    drum(k+1,l,c-1); }
}
int main()
{ freopen("alee.in","r", stdin);
  freopen("alee.out","w",stdout);
    int aux,m,i,j,x,y,x2,y2;
    scanf("%d %d",&n,&m);
   aux=n*n;
for(i=0;i<n;i++)
  for(j=0;j<n;j++)
    lb[i][j]=aux;
for(i=1;i<=m;i++)
  { scanf("%d %d",&x,&y);
    lb[x-1][y-1]=-1;}
    scanf("%d %d %d %d",&x,&y,&x2,&y2);
lb[x-1][y-1]=1;
drum(1,x-1,y-1);
printf("%d\n", lb[x2-1][y2-1]);
return 0;
}

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

#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;
}

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;
				}
			}
		}
	}
}

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

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;
}

#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;
}

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

#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;
}

#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;
}