Cod sursa(job #2999102)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 10 martie 2023 15:08:18
Problema Car Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.82 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[4];
std::bitset<NMAX> mat[NMAX];
char explored[NMAX][NMAX];

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<4;++cost)
	{
		while(!q[cost&3].empty())
		{
			lastCost=cost;
			p=q[cost&3].front();
			q[cost&3].pop();
			explored[p.i][p.j]|=1<<p.dir;
			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] & (1<<next.dir)))
					{
						q[(cost-k)&3].push(next);
					}
				}
				for(k=0;k<3;++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] & (1<<next.dir)))
					{
						q[(cost+k)&3].push(next);
					}
				}
			}
		}
	}
	if(!sol)
		fprintf(g, "-1");

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