Submission #252108

#	Time	Username	Problem	Language	Result	Execution time	Memory
252108		T0p_	Robots (APIO13_robots)	C++14	30 / 100	91 ms	163844 KiB

robots

#include<bits/stdc++.h>
using namespace std;

struct DJK
{
	int i;
	int j;
	int s;
	long long w;
	bool operator < (const DJK & o) const{
		return w > o.w;
	}
};

int n, m;
int di[4] = {-1, 0, 1, 0}, dj[4] = {0, 1, 0, -1};
long long dis[505][505][515];
pair<int, int> des[4][505][505];
char t[505][505];
queue<pair<int, int>> bfs;
priority_queue<DJK> djk;
bool visit[505][505][515];

pair<int, int> compute(int i, int j, int d)
{
	if(des[d][i][j].first) return des[d][i][j];
	int dd = d;
	if(t[i][j] == 'A')
	{
		dd += 3;
		dd %= 4;
	}
	else if(t[i][j] == 'C')
	{
		dd += 5;
		dd %= 4;
	}
	int ii = i + di[dd], jj = j + dj[dd];
	if(ii < 1 || jj < 1 || ii > n || jj > m || t[ii][jj] == 'x') return des[d][i][j] = {i, j};
	return des[d][i][j] = compute(ii, jj, dd);
}

int main()
{
	int K;
	scanf(" %d %d %d",&K,&m,&n);
	for(int i=1 ; i<=n ; i++)
		scanf(" %s",t[i]+1);
	for(int i=1 ; i<=n ; i++)
		for(int j=1 ; j<=m ; j++)
		{
			for(int k=1 ; k<(1<<K) ; k++) dis[i][j][k] = 1e9;
			if(t[i][j] == 'x') continue ;
			if('1' <= t[i][j] && t[i][j] <= '9')
			{
				int s = 1<<(t[i][j]-'0'-1);
				dis[i][j][s] = 0;
				djk.push({i, j, s, 0});
			}
			for(int k=0 ; k<4 ; k++)
				compute(i, j, k);
		}
	while(!djk.empty())
	{
		int i = djk.top().i;
		int j = djk.top().j;
		int s = djk.top().s;
		long long w = djk.top().w;
		djk.pop();
		if(visit[i][j][s]) continue ;
		visit[i][j][s] = true;
		if(s+1 == (1<<K))
		{
			printf("%d\n",w);
			return 0;
		}
		for(int k=0 ; k<4 ; k++)
		{
			int ii = des[k][i][j].first, jj = des[k][i][j].second;
			for(int it=0 ; it<(1<<K) ; it++)
			{
				int ss = it|s;
				if(dis[ii][jj][it] != 1e9 && dis[ii][jj][ss] > dis[ii][jj][it] + w + 1)
				{
					dis[ii][jj][ss] = dis[ii][jj][it] + w + 1;
					djk.push({ii, jj, ss, dis[ii][jj][ss]});
				}
			}
		}
	}
	printf("-1\n");
	return 0;
}

/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:74:19: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
    printf("%d\n",w);
                   ^
robots.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %d %d %d",&K,&m,&n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %s",t[i]+1);
   ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40