Cod sursa(job #2999081)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 10 martie 2023 14:50:44
Problema Car Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
//Ilie Dumitru
#include<cstdio>
#include<bitset>
#include<algorithm>
const int NMAX=505;
const int MAXDIMQ=NMAX*NMAX*8;

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

struct queue
{
	pos v[MAXDIMQ];
	int start, end;

	queue() : start(0), end(0) {}
	void push(pos x)
	{
		v[end]=x;
		end=(end+1)%MAXDIMQ;
	}
	pos pop()
	{
		int s=start;
		start=(start+1)%MAXDIMQ;
		return v[s];
	}
	bool empty()
	{
		if(end==start)
			return !(end=start=0);
		return 0;
	}
	void clear()
	{
		start=end=0;
	}
};

int N, M;
queue q[3];
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;
	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;!q[0].empty() || !q[1].empty() || !q[2].empty();++cost)
	{
		while(!q[cost%3].empty())
		{
			p=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);
				q[0].clear();
				q[1].clear();
				q[2].clear();
			}
			else
			{
				for(k=-2;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+std::abs(k))%3].push(next);
					}
				}
			}
		}
	}

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