Submission #909258

#	Time	Username	Problem	Language	Result	Execution time	Memory
909258		Jawad_Akbar_JJ	Robots (APIO13_robots)	C++17	0 / 100	17 ms	111196 KiB

robots

#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;

const int N = 505;
char a[N][N];
bool seen[5][N][N];

int x[N];
int y[N];
pair<int,int> tar[5][N][N];
int mn[100][N][N];
map<int,pair<int,int>> d;
map<pair<char,int>,int> chd;
int n,m;

bool valid(int i,int j,int cur){
	if (min(i,j) < 1 or i>n or j>m or a[i][j]=='x')
		return false;
	return true;
}

int dfs(int i,int j,int cur){
	seen[cur][i][j] = true;

	if (a[i][j] == 'A' or a[i][j] == 'C')
		cur = chd[{a[i][j],cur}];

	int ni = i + d[cur].first;
	int nj = j + d[cur].second;
	
	if (seen[cur][ni][nj]){
		int ncur = cur;
		if (a[ni][nj] == 'A' or a[ni][nj] == 'C')
			ncur = chd[{a[ni][nj],cur}];
		tar[cur][i][j] = tar[ncur][ni][nj];
		return cur;
	}
	
	if (!valid(ni,nj,cur)){
		tar[cur][i][j] = {i,j};
		return cur;
	}
	int ncur = dfs(ni,nj,cur);
	tar[cur][i][j] = tar[ncur][ni][nj];
	return cur;

}

// up 1
// left 2
// down 3
// right 4

void bfs(int ii,int jj,int cur,int init = 0){
	set<vector<int>> s;
	s.insert({init,ii,jj});
	mn[cur][ii][jj] = init;

	while (s.size()>0){
		vector<int> v = *begin(s);
		s.erase(begin(s));
		// if (cur/10 != cur%10)
		// cout<<v[0]<<" "<<v[1]<<" "<<v[2]<<endl;

		for (int i = 1;i<=4;i++){
			auto [ni,nj] = tar[i][v[1]][v[2]];
			if (ni == -1)
				continue;
			if (mn[cur][ni][nj] <= v[0])
				continue;
			mn[cur][ni][nj] = v[0] + 1;
			s.insert({v[0] + 1,ni,nj});
		}
	}
}

int main(){

	chd[{'A',1}] = 2;
	chd[{'A',2}] = 3;
	chd[{'A',3}] = 4;
	chd[{'A',4}] = 1;
	
	chd[{'C',2}] = 1;
	chd[{'C',3}] = 2;
	chd[{'C',4}] = 3;
	chd[{'C',1}] = 4;
	
	d[1] = {-1,0};
	d[2] = {0,-1};
	d[4] = {0,1};
	d[3] = {1,0};
	


	int k;
	cin>>k>>m>>n;

	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++){
			cin>>a[i][j];
			int c = a[i][j] - 48;
			if (isdigit(a[i][j]))
				x[c] = i,y[c] = j;
		}

	for (int cur=1;cur<=4;cur++)
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++)
				tar[cur][i][j] = {-1,-1};

	for (int cur=1;cur<=4;cur++)
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++)
				if (!seen[cur][i][j])
					dfs(i,j,cur);

	// for (int i = 1;i<=4;i++){
	// 	auto [ni,nj] = tar[i][4][1];
	// 	cout<<ni<<" "<<nj<<endl;
	// }
	// return 0;
	for (int cur=1;cur<100;cur++)
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++)
				mn[cur][i][j] = 1e8;

	for (int i=1;i<=k;i++){
		// cout<<endl<<i<<i<<" "<<x[i]<<" "<<y[i]<<" "<<endl;
		bfs(x[i],y[i],i * 10 + i);
	}

	for (int i=k;i>=1;i--){
		for (int j=i+1;j<=k;j++){
			int Mn = 1e8;
			int row = -1,col = -1;
			for (int l=i;l<j;l++){
				for (int r=1;r<=n;r++){
					for (int c=1;c<=m;c++){
						int f = i * 10 + l;
						int s = (l + 1) * 10 + j;
						// if (i==3 and j==4)
						// 	cout<<"fghjhgfdfghj "<<f<<" "<<s<<" "<<r<<" "<<c<<" "<<mn[f][r][c] + mn[s][r][c]<<endl;
						if (mn[f][r][c] + mn[s][r][c] < Mn)
							Mn = mn[f][r][c] + mn[s][r][c],row = r,col = c;
					}// for c
				} // for r
			}// for l
			if (row != -1){
				// cout<<endl<<i<<j<<" "<<Mn<<" "<<row<<" "<<col<<endl;
				bfs(row,col,i * 10 + j,Mn);
			}
		}// for j
	} // for i
	int ans = 1e7;

	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			ans = min(ans,mn[10 + k][i][j]);
	if (ans == 1e7)
		ans = -1;
	cout<<ans<<endl;
}

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