Submission #364480

#	Time	Username	Problem	Language	Result	Execution time	Memory
364480		AriaH	Robots (APIO13_robots)	C++11	0 / 100	80 ms	124524 KiB

robots

/** Im the best because i work as hard as i possibly can **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl                        "\n"

const int N = 5e2 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 5e8;
const int LOG = 22;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

char C[N];

string S[N];

int n, m, k, mark[N][N], dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0}, dp[11][11][N][N], dis[N][N];

pii f[4][N][N], emp = {0, 0};

pii dfs(int d, int x, int y)
{
	if(f[d][x][y] != emp) return f[d][x][y];
	pii &cu = f[d][x][y];
	if(mark[x][y]) return cu = Mp(x, y);
	mark[x][y] = 1;
	if(S[x][y] == 'A' || S[x][y] == 'C')
	{
		int d2 = d + (S[x][y] == 'A'? 1 : -1);
		d2 = (d2 + 4) % 4;
		int x2 = x + dx[d2], y2 = y + dy[d2];
		if(S[x2][y2] == '#') cu = Mp(x, y);
		else cu = dfs(d2, x2, y2);
	}
	else
	{
		int x2 = x + dx[d], y2 = y + dy[d];
		if(S[x2][y2] == '#') cu = Mp(x, y);
		else cu = dfs(d, x2, y2);
	}
	mark[x][y] = 0;
	return cu;
}

int main()
{
	scanf("%d%d%d", &k, &m, &n);
	for(int i = 1; i <= n; i ++)
	{
		scanf("%s", C);
		S[i] = C;
		S[i] = "#" + S[i] + "#";
	}
	for(int j = 0; j <= m; j ++) S[0][j] = S[n + 1][j] = '#';
	for(int i = 1; i <= n; i ++)
	{
		for(int j = 1; j <= m; j ++)
		{
			if(S[i][j] != '#')
			{
				for(int d = 0; d < 4; d ++)
				{
					f[d][i][j] = dfs(d, i, j);
				}
			}
		}
	}
	for(int i = 0; i < 11; i ++)
	{
		for(int j = 0; j < 11; j ++)
		{
			for(int K = 0; K < N; K ++)
			{
				for(int t = 0; t < N; t ++)
				{
					dp[i][j][K][t] = inf;
				}
			}
		}
	}
	for(int i = 1; i <= n; i ++)
	{
		for(int j = 1; j <= m; j ++)
		{
			if('1' <= S[i][j] && S[i][j] <= '9')
			{
				dp[S[i][j] - '0'][S[i][j] - '0'][i][j] = 0;
			}
		}
	}
	/*
	for(int i = 1; i <= n; i ++)
	{
		for(int j = 1; j <= m; j ++)
		{
			printf("i = %d j = %d : %d %d  %d %d   %d %d  %d %d\n", i, j, f[0][i][j].F, f[0][i][j].S, f[1][i][j].F, f[1][i][j].S, f[2][i][j].F, f[2][i][j].S,  f[3][i][j].F, f[3][i][j].S);
		}
	}
	*/
	for(int tool = 1; tool <= k; tool ++)
	{
		for(int l = 1; l <= k - tool + 1; l ++)
		{
			set < pair < int, pii > > st;
			for(int i = 0; i < N; i ++)
			{
				for(int j = 0; j < N; j ++) 
				{
					dis[i][j] = inf;
				}
			}
			int r = l + tool - 1;
			for(int i = 1; i <= n; i ++)
			{
				for(int j = 1; j <= m; j ++)
				{
					for(int mid = l; mid < r; mid ++)
					{
						dp[l][r][i][j] = min(dp[l][r][i][j], dp[l][mid][i][j] + dp[mid + 1][r][i][j]);
					}
					dis[i][j] = dp[l][r][i][j];
					if(dis[i][j] < inf) st.insert(Mp(dis[i][j], Mp(i, j)));
				}
			}
			while(!st.empty())
			{
				pair < int, pii > cu = *st.begin();
				int x = cu.S.F, y = cu.S.S;
				st.erase(st.begin());
				for(int d = 0; d < 4; d ++)
				{
					pii now = f[d][x][y];
					if(S[now.F][now.S] == '#' || now == emp) continue;
					if(dis[now.F][now.S] > dis[x][y] + 1)
					{
						dis[now.F][now.S] = dis[x][y] + 1;
						st.insert(Mp(dis[now.F][now.S], now));
					}
				}
			}
			for(int i = 0; i < N; i ++)
			{
				for(int j = 0; j < N; j ++)
				{
					dp[l][r][i][j] = dis[i][j];
				}
			}
		}
	}
	int tot = inf;
	for(int i = 1; i <= n; i ++)
	{
		for(int j = 1; j <= m; j ++)
		{
			tot = min(tot, dp[1][k][i][j]);
		}
	}
	if(tot >= inf) tot = -1;
	printf("%d\n", tot);
    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:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |  scanf("%d%d%d", &k, &m, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
robots.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |   scanf("%s", C);
      |   ~~~~~^~~~~~~~~

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