답안 #385565

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
385565 2021-04-04T15:16:00 Z ogibogi2004 로봇 (APIO13_robots) C++14
30 / 100
315 ms 163840 KB
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("O3")
#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];
vector<pair<int,int> >g1[502][502];
char table[502][502];
int r,n,m;
vector<pair<pair<int,int>,char> >ends;
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];
int c(int x,int y)
{
	return number[x][y];
}
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);
		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])
		{
			nxt[xd.first.first][xd.first.second][xd.second]=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=nxt[i][j][l].first.first;
				y=nxt[i][j][l].first.second;
				z=nxt[i][j][l].second;
				if(x==i&&y==j&&z==l)continue;
				g1[i][j].push_back({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[c(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[c(i,i)][x][y]=0;
		while(!q.empty())
		{
			tie(x,y)=q.front();
			q.pop();
			for(auto xd:g1[x][y])
			{
				if(dp[c(i,i)][xd.first][xd.second]>dp[c(i,i)][x][y]+1)
				{
					dp[c(i,i)][xd.first][xd.second]=dp[c(i,i)][x][y]+1;
					q.push(xd);
				}
			}
		}
	}
	queue<pair<int,int> >qqq;
	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=c(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[c(r1,mid)][i][j]+dp[c(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)
			{
				for(auto xd:pq[mindp])qqq.push({xd.first,xd.second});
				pq[mindp].clear();
			}
			while(!qqq.empty())
			{
				int x,y;
				tie(x,y)=qqq.front();
				qqq.pop();
				for(auto xd:g1[x][y])
				{
					if(dp[cc][x][y]+1<dp[cc][xd.first][xd.second])
					{
						dp[cc][xd.first][xd.second]=dp[cc][x][y]+1;
						qqq.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;
						qqq.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[c(1,r)][i][j]);
		}
	}
	if(ans==INF)cout<<"-1\n";
	else 
	{
		cout<<ans<<endl;
	}
return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:88:73: warning: array subscript has type 'char' [-Wchar-subscripts]
   88 |     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:96:43: warning: array subscript has type 'char' [-Wchar-subscripts]
   96 |   nxt[xd.first.first][xd.first.second][xd.second]=xd;
      |                                        ~~~^~~~~~
robots.cpp:102:50: warning: array subscript has type 'char' [-Wchar-subscripts]
  102 |   for(auto xd:g[u.first.first][u.first.second][u.second])
      |                                                ~~^~~~~~
robots.cpp:104:44: warning: array subscript has type 'char' [-Wchar-subscripts]
  104 |    nxt[xd.first.first][xd.first.second][xd.second]=nxt[u.first.first][u.first.second][u.second];
      |                                         ~~~^~~~~~
robots.cpp:104:89: warning: array subscript has type 'char' [-Wchar-subscripts]
  104 |    nxt[xd.first.first][xd.first.second][xd.second]=nxt[u.first.first][u.first.second][u.second];
      |                                                                                       ~~^~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 88684 KB Output is correct
2 Correct 60 ms 88684 KB Output is correct
3 Correct 61 ms 88684 KB Output is correct
4 Correct 61 ms 88812 KB Output is correct
5 Correct 60 ms 88812 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 88684 KB Output is correct
2 Correct 60 ms 88684 KB Output is correct
3 Correct 61 ms 88684 KB Output is correct
4 Correct 61 ms 88812 KB Output is correct
5 Correct 60 ms 88812 KB Output is correct
6 Correct 60 ms 88684 KB Output is correct
7 Correct 60 ms 88684 KB Output is correct
8 Correct 65 ms 88684 KB Output is correct
9 Correct 56 ms 88684 KB Output is correct
10 Correct 60 ms 88812 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 88684 KB Output is correct
2 Correct 60 ms 88684 KB Output is correct
3 Correct 61 ms 88684 KB Output is correct
4 Correct 61 ms 88812 KB Output is correct
5 Correct 60 ms 88812 KB Output is correct
6 Correct 60 ms 88684 KB Output is correct
7 Correct 60 ms 88684 KB Output is correct
8 Correct 65 ms 88684 KB Output is correct
9 Correct 56 ms 88684 KB Output is correct
10 Correct 60 ms 88812 KB Output is correct
11 Runtime error 315 ms 163840 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 88684 KB Output is correct
2 Correct 60 ms 88684 KB Output is correct
3 Correct 61 ms 88684 KB Output is correct
4 Correct 61 ms 88812 KB Output is correct
5 Correct 60 ms 88812 KB Output is correct
6 Correct 60 ms 88684 KB Output is correct
7 Correct 60 ms 88684 KB Output is correct
8 Correct 65 ms 88684 KB Output is correct
9 Correct 56 ms 88684 KB Output is correct
10 Correct 60 ms 88812 KB Output is correct
11 Runtime error 315 ms 163840 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -