oj.uz

답안 #385571

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
385571 2021-04-04T15:24:47 Z ogibogi2004 로봇 (APIO13_robots) C++14
60 / 100
 332 ms 163844 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
#pragma GCC target ("fma,avx,avx2")
#define ends dfdsfdsf
const int INF=1e8;
pair<pair<int,int>,char> nxt[502][502][4];
vector<pair<pair<int,int>,char> >g[502][502][4];
pair<int,int>g1[502][502][4];
int deg[502][502];
char table[502][502];
int r,n,m;
vector<pair<pair<int,int>,char> >ends;
pair<pair<int,int>,char> actual_nxt[502][502][4];
bool not_valid(pair<int,int> p)
{
	int x=p.first,y=p.second;
	if(x<1||y<1||x>n||y>m)return 1;
	return table[x][y]=='x';
}
int dp[45][502][502];
pair<int,int> where[10];
int number[10][10];
void pre()
{
	int cnt=0;
	for(int i=1;i<=9;++i)
	{
		for(int j=i;j<=9;++j)
		{
			number[i][j]=++cnt;
		}
	}
}
vector<pair<int,int> >pq[2500000];
int main()
{
	pre();
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>r>>m>>n;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			cin>>table[i][j];
			if(isdigit(table[i][j]))
			{
				where[table[i][j]-'0']={i,j};
			}
		}
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			if(table[i][j]=='x')continue;
			if(table[i][j]=='A')
			{
				nxt[i][j][0]={{i,j-1},3};
				nxt[i][j][1]={{i-1,j},0};
				nxt[i][j][2]={{i,j+1},1};
				nxt[i][j][3]={{i+1,j},2};
			}
			else if(table[i][j]=='C')
			{
				nxt[i][j][0]={{i,j+1},1};
				nxt[i][j][1]={{i+1,j},2};
				nxt[i][j][2]={{i,j-1},3};
				nxt[i][j][3]={{i-1,j},0};
			}
			else
			{
				nxt[i][j][0]={{i-1,j},0};
				nxt[i][j][1]={{i,j+1},1};
				nxt[i][j][2]={{i+1,j},2};
				nxt[i][j][3]={{i,j-1},3};
			}
			for(int l=0;l<4;++l)
			{
				if(not_valid(nxt[i][j][l].first))
				{
					ends.push_back({{i,j},l});
				}
				g[nxt[i][j][l].first.first][nxt[i][j][l].first.second][nxt[i][j][l].second].push_back({{i,j},l});
			}
		}
	}
	queue<pair<pair<int,int>,char> >qq;
	for(auto xd:ends)
	{
		qq.push(xd);
		actual_nxt[xd.first.first][xd.first.second][xd.second]=xd;
	}
	while(!qq.empty())
	{
		auto u=qq.front();
		qq.pop();
		for(auto xd:g[u.first.first][u.first.second][u.second])
		{
			actual_nxt[xd.first.first][xd.first.second][xd.second]=actual_nxt[u.first.first][u.first.second][u.second];
			qq.push(xd);
		}
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			for(int l=0;l<4;++l)
			{
				int x,y,z;
				x=actual_nxt[i][j][l].first.first;
				y=actual_nxt[i][j][l].first.second;
				z=actual_nxt[i][j][l].second;
				if(x==i&&y==j&&z==l)continue;
				g1[i][j][deg[i][j]++]={x,y};
			}
		}
	}
	for(int r1=1;r1<=r;++r1)
	{
		for(int r2=1;r2<=r;++r2)
		{
			for(int i1=1;i1<=n;++i1)
			{
				for(int i2=1;i2<=m;++i2)
				{
					dp[number[r1][r2]][i1][i2]=INF;
				}
			}
		}
	}
	queue<pair<int,int> >q;
	for(int i=1;i<=r;++i)
	{
		int x,y;
		x=where[i].first;
		y=where[i].second;
		q.push({x,y});
		dp[number[i][i]][x][y]=0;
		while(!q.empty())
		{
			tie(x,y)=q.front();
			q.pop();
			for(int jj=0;jj<deg[x][y];jj++)
			{
				pair<int,int> xd=g1[x][y][jj];
				if(dp[number[i][i]][xd.first][xd.second]>dp[number[i][i]][x][y]+1)
				{
					dp[number[i][i]][xd.first][xd.second]=dp[number[i][i]][x][y]+1;
					q.push(xd);
				}
			}
		}
	}
	vector<int>dps;
	for(int len=2;len<=r;++len)
	{
		for(int r1=1;r1+len-1<=r;++r1)
		{
			int r2=r1+len-1;
			int cc=number[r1][r2];
			for(int mid=r1;mid<r2;++mid)
			{
				for(int i=1;i<=n;++i)
				{
					for(int j=1;j<=m;++j)
					{
						dp[cc][i][j]=min(dp[cc][i][j],dp[number[r1][mid]][i][j]+dp[number[mid+1][r2]][i][j]);
					}
				}
			}
			int mindp=INF;
			for(int i=1;i<=n;++i)
			{
				for(int j=1;j<=m;++j)
				{
					mindp=min(mindp,dp[cc][i][j]);
					if(dp[cc][i][j]<INF)
					{
						pq[dp[cc][i][j]].push_back({i,j});
						dps.push_back(dp[cc][i][j]);
					}
				}
			}
			if(mindp>=INF)continue;
			for(auto xd:pq[mindp])q.push({xd.first,xd.second});
			pq[mindp].clear();
			while(!q.empty())
			{
				int x,y;
				tie(x,y)=q.front();
				q.pop();
				for(int jj=0;jj<deg[x][y];jj++)
				{
					pair<int,int> xd=g1[x][y][jj];
					if(dp[cc][x][y]+1<dp[cc][xd.first][xd.second])
					{
						dp[cc][xd.first][xd.second]=dp[cc][x][y]+1;
						q.push(xd);
					}
				}
				if(dp[cc][x][y]+1<INF&&pq[dp[cc][x][y]+1].size()!=0)
				{
					for(auto xd:pq[dp[cc][x][y]+1])
					{
						if(dp[cc][xd.first][xd.second]!=dp[cc][x][y]+1)continue;
						q.push(xd);
					}
					pq[dp[cc][x][y]+1].clear();
				}
			}
			for(auto xd:dps)pq[xd].clear();
			dps.clear();
		}
	}
	/*for(int i1=1;i1<=r;i1++)
	{
		for(int i2=i1;i2<=r;i2++)
		{
			cout<<i1<<"-"<<i2<<endl;
			for(int i=1;i<=n;i++)
			{
				for(int j=1;j<=m;j++)
				{
					if(dp[i1][i2][i][j]<INF)cout<<dp[i1][i2][i][j];
					else cout<<"x";
				}
				cout<<endl;
			}
		}
	}*/
	int ans=INF;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=m;++j)
		{
			ans=min(ans,dp[number[1][r]][i][j]);
		}
	}
	if(ans==INF)cout<<"-1\n";
	else 
	{
		cout<<ans<<'\n';
	}
return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:86:73: warning: array subscript has type 'char' [-Wchar-subscripts]
   86 |     g[nxt[i][j][l].first.first][nxt[i][j][l].first.second][nxt[i][j][l].second].push_back({{i,j},l});
      |                                                            ~~~~~~~~~~~~~^~~~~~
robots.cpp:94:50: warning: array subscript has type 'char' [-Wchar-subscripts]
   94 |   actual_nxt[xd.first.first][xd.first.second][xd.second]=xd;
      |                                               ~~~^~~~~~
robots.cpp:100:50: warning: array subscript has type 'char' [-Wchar-subscripts]
  100 |   for(auto xd:g[u.first.first][u.first.second][u.second])
      |                                                ~~^~~~~~
robots.cpp:102:51: warning: array subscript has type 'char' [-Wchar-subscripts]
  102 |    actual_nxt[xd.first.first][xd.first.second][xd.second]=actual_nxt[u.first.first][u.first.second][u.second];
      |                                                ~~~^~~~~~
robots.cpp:102:103: warning: array subscript has type 'char' [-Wchar-subscripts]
  102 |    actual_nxt[xd.first.first][xd.first.second][xd.second]=actual_nxt[u.first.first][u.first.second][u.second];
      |                                                                                                     ~~^~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 82796 KB Output is correct
2 Correct 56 ms 82796 KB Output is correct
3 Correct 58 ms 82796 KB Output is correct
4 Correct 58 ms 83052 KB Output is correct
5 Correct 60 ms 83052 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 82796 KB Output is correct
2 Correct 56 ms 82796 KB Output is correct
3 Correct 58 ms 82796 KB Output is correct
4 Correct 58 ms 83052 KB Output is correct
5 Correct 60 ms 83052 KB Output is correct
6 Correct 56 ms 82796 KB Output is correct
7 Correct 56 ms 82796 KB Output is correct
8 Correct 59 ms 82796 KB Output is correct
9 Correct 59 ms 82796 KB Output is correct
10 Correct 56 ms 83052 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 82796 KB Output is correct
2 Correct 56 ms 82796 KB Output is correct
3 Correct 58 ms 82796 KB Output is correct
4 Correct 58 ms 83052 KB Output is correct
5 Correct 60 ms 83052 KB Output is correct
6 Correct 56 ms 82796 KB Output is correct
7 Correct 56 ms 82796 KB Output is correct
8 Correct 59 ms 82796 KB Output is correct
9 Correct 59 ms 82796 KB Output is correct
10 Correct 56 ms 83052 KB Output is correct
11 Correct 152 ms 132512 KB Output is correct
12 Correct 88 ms 103712 KB Output is correct
13 Correct 112 ms 123424 KB Output is correct
14 Correct 219 ms 134944 KB Output is correct
15 Correct 131 ms 130080 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 82796 KB Output is correct
2 Correct 56 ms 82796 KB Output is correct
3 Correct 58 ms 82796 KB Output is correct
4 Correct 58 ms 83052 KB Output is correct
5 Correct 60 ms 83052 KB Output is correct
6 Correct 56 ms 82796 KB Output is correct
7 Correct 56 ms 82796 KB Output is correct
8 Correct 59 ms 82796 KB Output is correct
9 Correct 59 ms 82796 KB Output is correct
10 Correct 56 ms 83052 KB Output is correct
11 Correct 152 ms 132512 KB Output is correct
12 Correct 88 ms 103712 KB Output is correct
13 Correct 112 ms 123424 KB Output is correct
14 Correct 219 ms 134944 KB Output is correct
15 Correct 131 ms 130080 KB Output is correct
16 Runtime error 332 ms 163844 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -