Cod sursa(job #631516)

Utilizator darkseekerBoaca Cosmin darkseeker Data 8 noiembrie 2011 12:57:01
Problema Nums Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <fstream>
using namespace std;

const int NMAX = 55;

bool viz[NMAX][NMAX][NMAX][NMAX];
char board[NMAX][NMAX],line[NMAX];
int fline,fcolumn,sline,scolumn,solLine,solColumn,N,M;

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

struct state{
	short fline,fcolumn,sline,scolumn,lg;
};

int main()
{
	int i,lg,j;
	int start = 1 ,final = 1;
	state Q[NMAX * NMAX * NMAX * NMAX];
	state curent,next;
	bool solved = 0;
	
	fin>>N>>M;
	fin.get();
	
	for(i = 1; i <= N; i++)
	{
		fin.get(line,NMAX,'\n');
		fin.get();
		
		for(j=0; j<M; j++)
		{
			board[i][j+1] = line[j];
			if(line[j] == '.')
				fline = i,fcolumn = j+1;
			if(line[j] == 'X')
				sline = i,scolumn = j+1;
		}
		
	}
	
	solLine = 1;
	solColumn = 1;
	
	int ldir[] = {-1,1,0,0};
	int cdir[] = {0,0,-1,1};
	
	Q[start].fline = fline;
	Q[start].fcolumn = fcolumn;
	Q[start].sline = sline;
	Q[start].scolumn = scolumn;
	Q[start].lg = 0;
	viz[fline][fcolumn][sline][scolumn] = 1;
	
	while(start <= final && !solved)
	{
		curent = Q[start];
		board[curent.fline][curent.fcolumn] = '.';
		board[curent.sline][curent.scolumn] = 'X';
		
		for(i=0; i<4 && !solved; i++)
			{
				if(board[curent.fline + ldir[i]][curent.fcolumn + cdir[i]] == '*')
					if(!viz[curent.fline + ldir[i]][curent.fcolumn + cdir[i]][sline][scolumn])
					{
						Q[++final].fline = curent.fline + ldir[i];
						Q[final].fcolumn = curent.fcolumn + cdir[i];
						Q[final].sline = curent.sline;
						Q[final].scolumn = curent.scolumn;
						Q[final].lg = curent.lg + 1;
						viz[curent.fline + ldir[i]][curent.fcolumn + cdir[i]][sline][scolumn] = 1;
						
						if(Q[final].sline == solLine && Q[final].scolumn == solColumn)
							solved = 1;
					}
				if(board[curent.fline + ldir[i]][curent.fcolumn + cdir[i]] == 'X')
					if(!viz[curent.fline + ldir[i]][curent.fcolumn + cdir[i]][curent.fline][curent.fcolumn])
					{
						viz[curent.fline + ldir[i]][curent.fcolumn + cdir[i]][curent.fline][curent.fcolumn] = 1;
						Q[++final].fline = curent.fline + ldir[i];
						Q[final].fcolumn = curent.fcolumn + cdir[i];
						Q[final].sline = curent.fline;
						Q[final].scolumn = curent.scolumn;
						Q[final].lg = curent.lg + 1;
						
						if(Q[final].sline == solLine && Q[final].scolumn == solColumn)
							solved = 1;
					}
		}
				
		board[curent.fline][curent.fcolumn] = '*';
		board[curent.sline][curent.scolumn] = '*';
		start++;
	}
	
	if(solved)
		fout<<Q[final].lg<<'\n';
	else
		fout<<"Impossible"<<'\n';
	
	fin.close();
	fout.close();
	return 0;
}