Cod sursa(job #563326)

Utilizator borsoszalanBorsos Zalan borsoszalan Data 24 martie 2011 22:22:56
Problema Shop Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include<stdio.h>
#include<queue>
#define mp make_pair

using namespace std;

queue<pair<int, int> > q1;
queue<int> q2;


int n,m,i,j,s1,o1,s2,o2, x,y;
char t[1002][1002];
int nr=0, nod;
bool viz[1002][1001];

void fill(int i, int j)
{
	if(!viz[i][j]&&i>=1&&i<=n&&j>=1&&j<=m&&t[i][j]==t[x][y])
	{
		viz[i][j]=true;
		q1.push(mp(i,j));
		q2.push(q2.front());
		fill(i-1,j);fill(i+1,j);fill(i, j-1);fill(i, j+1);
	}
}

int main()
{
	freopen("padure.in", "r", stdin);
	freopen("padure.out", "w", stdout);
	scanf("%d%d%d%d%d%d", &n, &m, &s1, &o1, &s2, &o2);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			scanf("%d", &t[i][j]);
	q1.push(mp(s1,o1));
	q2.push(0);
	viz[s1][o1]=true;
	while(!viz[s2][o2])
	{
		x=q1.front().first;
		y=q1.front().second;
		fill(x-1,y);
		fill(x+1,y);
		fill(x,y-1);
		fill(x,y+1);
		if(x>1&&!viz[x-1][y])
		{
			q1.push(mp(x-1,y));
			q2.push(q2.front()+1);
			viz[x-1][y]=true;
		}
		if(x<n&&!viz[x+1][y])
		{
			q1.push(mp(x+1,y));
			q2.push(q2.front()+1);
			viz[x+1][y]=true;
		}
		if(y>1&&!viz[x][y-1])
		{
			q1.push(mp(x,y-1));
			q2.push(q2.front()+1);
			viz[x][y-1]=true;
		}
		if(y<m&&!viz[x][y+1])
		{
			q1.push(mp(x,y+1));
			q2.push(q2.front()+1);
			viz[x][y+1]=true;
		}
		q1.pop();q2.pop();

	}
	while(q1.front().first!=s2&&q1.front().second!=o2)
	{
		q1.pop();
		q2.pop();
	}
	printf("%d", q2.front());
	return 0;
}