Cod sursa(job #2999125)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 10 martie 2023 15:28:48
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.85 kb
//Ilie Dumitru
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<queue>
const int NMAX=505;
const int MAXDIMQ=NMAX*NMAX*8;

struct pos
{
	int i, j, dir;
};

int N, M;
std::queue<pos> q[3];
std::bitset<NMAX> mat[NMAX];
bool explored[NMAX][NMAX][8];

int main()
{
	FILE *f=fopen("car.in", "r"), *g=fopen("car.out", "w");
	int i, j, i0, i1, j0, j1, k, cost, x, lastCost=0;
	bool sol=0;
	pos p, next;
	const int di[8]={0, 1, 1, 1, 0, -1, -1, -1};
	const int dj[8]={1, 1, 0, -1, -1, -1, 0, 1};

	fscanf(f, "%d%d%d%d%d%d", &N, &M, &i0, &j0, &i1, &j1);
	for(i=0;i<N;++i)
	{
		for(j=0;j<M;++j)
		{
			fscanf(f, "%d", &x);
			mat[i][j]=x;
		}
	}

	for(i=0;i<8;++i)
		q[0].push({i0-1, j0-1, i});

	for(cost=0;cost-lastCost<3;++cost)
	{
		while(!q[cost%3].empty())
		{
			lastCost=cost;
			p=q[cost%3].front();
			q[cost%3].pop();
			if(!explored[p.i][p.j][p.dir])
			{
				explored[p.i][p.j][p.dir]=1;
				if(p.i==i1-1 && p.j==j1-1)
				{
					fprintf(g, "%d\n", cost);
					sol=1;
					while(!q[0].empty())
						q[0].pop();
					while(!q[1].empty())
						q[1].pop();
					while(!q[2].empty())
						q[2].pop();
				}
				else
				{
					for(k=-2;k<0;++k)
					{
						next.i=p.i+di[(p.dir+k+8)&7];
						next.j=p.j+dj[(p.dir+k+8)&7];
						next.dir=(p.dir+k+8)&7;
						if(next.i>-1 && next.i<N && next.j>-1 && next.j<M && !mat[next.i][next.j] && !explored[next.i][next.j][next.dir])
							q[(cost-k)%3].push(next);
					}
					for(k=0;k<3;++k)
					{
						next.i=p.i+di[(p.dir+k)&7];
						next.j=p.j+dj[(p.dir+k)&7];
						next.dir=(p.dir+k+8)&7;
						if(next.i>-1 && next.i<N && next.j>-1 && next.j<M && !mat[next.i][next.j] && !explored[next.i][next.j][next.dir])
							q[(cost+k)%3].push(next);
					}
				}
			}
		}
	}
	if(!sol)
		fprintf(g, "-1");

	fclose(f);
	fclose(g);
	return 0;
}