Submission #93258

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
93258	2019-01-07T11:17:12 Z	KLPP	Robots (APIO13_robots)	C++14	Compilation error	0 ms	0 KB

robots

#include<iostream>
#include<queue>
using namespace std;
typedef pair<short int,short int> pii;
int n,m,r;
char grid[500][500];
pii moves[500][500][4];
int DP[500][500][9][9];
bool computed[9][9];
priority_queue<pair<int,pii> >pq;
pii ans;
int prevdir;
pii Move(int a, int b,int dir){
	//cout<<a<<" "<<b<<" "<<dir<<endl;
	if(a<0 || n<=a || b<0 || m<=b)return pii(-1,-1);
	if(moves[a][b][dir].first!=-1)return moves[a][b][dir];
	if(grid[a][b]=='x')return pii(-1,-1);
	prevdir=dir;
	if(grid[a][b]=='A'){
		dir+=3;
		dir%=4;
	}
	if(grid[a][b]=='C'){
		dir++;
		dir%=4;
	}
	if(dir==0){
		ans=Move(a,b+1,dir);	
	}if(dir==1){
		ans=Move(a+1,b,dir);
	}if(dir==2){
		ans=Move(a,b-1,dir);
	}if(dir==3){
		ans=Move(a-1,b,dir);
	}
	if(ans.first==-1){
		ans=pii(a,b);
	}
	moves[a][b][prevdir]=ans;
	return ans;
}
int d;
pii pos,next;
int x,y;
void compute(int a, int b){
	
	if(computed[a][b])return;
	for(int med=a;med<b;med++){
		compute(a,med);
		compute(med+1,b);
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				DP[i][j][a][b]=min(DP[i][j][a][b],DP[i][j][a][med]+DP[i][j][med+1][b]);
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			pq.push(pair<int,pii>(DP[i][j][a][b],pii(i,j)));
		}
	}
	while(!pq.empty()){
		d=pq.top().first;
		pos=pq.top().second;
		pq.pop();
		x=pos.first;
		y=pos.second;
		if(d>DP[x][y][a][b])continue;
		for(int dir=0;dir<4;dir++){
			next=Move(x,y,dir);
			if(DP[next.first][next.second][a][b]>d+1){
				DP[next.first][next.second][a][b]=d+1;
				pq.push(pair<int,pii>(d+1,next));
			}
		}
	}
	computed[a][b]=true;
}
int main(){
	cin>>r>>m>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			for(int k=0;k<4;k++)moves[i][j][k]=pii(-1,-1);
			cin>>grid[i][j];
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			for(int k=0;k<r;k++){
				for(int l=k;l<r;l++){
					DP[i][j][k][l]=1000000000;
				}
			}
		}
	}
	for(int k=0;k<r;k++){
		for(int l=k;l<r;l++){computed[k][l]=false;
			
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(grid[i][j]>='0' && grid[i][j]<='9'){
				DP[i][j][grid[i][j]-'1'][grid[i][j]-'1']=0;
			}
		}
	}
	compute(0,r-1);
	int ans=1000000000;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			ans=min(ans,DP[i][j][0][r-1]);
			//cout<<DP[i][j][0][r-1]<<" ";
		}//cout<<endl;
	}cout<<ans<<endl;
	//cout<<Move(0,0,2).first<<" "<<Move(0,0,2).second<<endl;
	return 0;
}

Compilation message

robots.cpp: In function 'void compute(int, int)':
robots.cpp:70:4: error: reference to 'next' is ambiguous
    next=Move(x,y,dir);
    ^~~~
robots.cpp:43:9: note: candidates are: pii next
 pii pos,next;
         ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from robots.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
robots.cpp:71:10: error: reference to 'next' is ambiguous
    if(DP[next.first][next.second][a][b]>d+1){
          ^~~~
robots.cpp:43:9: note: candidates are: pii next
 pii pos,next;
         ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from robots.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
robots.cpp:71:22: error: reference to 'next' is ambiguous
    if(DP[next.first][next.second][a][b]>d+1){
                      ^~~~
robots.cpp:43:9: note: candidates are: pii next
 pii pos,next;
         ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from robots.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
robots.cpp:72:8: error: reference to 'next' is ambiguous
     DP[next.first][next.second][a][b]=d+1;
        ^~~~
robots.cpp:43:9: note: candidates are: pii next
 pii pos,next;
         ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from robots.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
robots.cpp:72:20: error: reference to 'next' is ambiguous
     DP[next.first][next.second][a][b]=d+1;
                    ^~~~
robots.cpp:43:9: note: candidates are: pii next
 pii pos,next;
         ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from robots.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~
robots.cpp:73:26: error: expected primary-expression before '(' token
     pq.push(pair<int,pii>(d+1,next));
                          ^
robots.cpp:73:31: error: reference to 'next' is ambiguous
     pq.push(pair<int,pii>(d+1,next));
                               ^~~~
robots.cpp:43:9: note: candidates are: pii next
 pii pos,next;
         ^~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:66:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from robots.cpp:1:
/usr/include/c++/7/bits/stl_iterator_base_funcs.h:208:5: note:                 template<class _ForwardIterator> _ForwardIterator std::next(_ForwardIterator, typename std::iterator_traits<_Iter>::difference_type)
     next(_ForwardIterator __x, typename
     ^~~~