Pagini recente » Cod sursa (job #2702705) | Cod sursa (job #719103) | Cod sursa (job #2165934) | Cod sursa (job #674922) | Cod sursa (job #631516)
Cod sursa(job #631516)
#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;
}