// 2
#ifndef LOCAL
#define NDEBUG 1
#endif
#include<bits/stdc++.h>
int numRobot, numRow, numCol;
std::vector<std::vector<char>> data;
struct Pos{
int row, col;
int index() const{
assert((unsigned) row<(unsigned) numRow); assert((unsigned) col<(unsigned) numCol);
return col+numCol*row;
}
};
struct State{
int dir; // dir+1: clockwise
int row, col;
std::pair<int, int> dirVector() const{
std::pair<int, int> result{1, 0};
switch(dir){
case 3: result={result.second,-result.first};
case 2: result={result.second,-result.first};
case 1: result={result.second,-result.first};
case 0: return result;
}
assert(false);
}
int index() const{return dir+4*Pos{row, col}.index();}
};
int const loop=-2, uncomputed=-1;
std::vector<int> memory;
int compute(State it){
auto& curMemory=memory[it.index()];
if(curMemory!=uncomputed) return curMemory;
State next=it;
switch(data[next.row][next.col]){
case 'A':
next.dir=(next.dir-1)&3; break;
case 'C':
next.dir=(next.dir+1)&3; break;
case 'x':
assert(false); __builtin_unreachable();
}
next.row+=next.dirVector().first; next.col+=next.dirVector().second;
if((unsigned)next.row>=(unsigned)numRow or (unsigned)next.col>=(unsigned)numCol or
data[next.row][next.col]=='x')
return curMemory=Pos{it.row, it.col}.index();
curMemory=loop;
return curMemory=compute(next);
}
int getMemory(int pos, int dir){
int result=memory[dir+4*pos];
assert(result!=uncomputed);
return result;
}
int main(){
std::ios::sync_with_stdio(0);std::cin.tie(0);
std::cin>>numRobot>>numCol>>numRow;
if(numRobot==1){std::cout<<"0\n"; return 0;}
data.resize(numRow);
for(auto& row: data){
row.resize(numCol+1);
std::cin>>row.data();
assert(row.back()==0); row.pop_back();
assert(row.back()!=0);
}
memory.assign(numRow*numCol*4, uncomputed);
for(int row=0; row<numRow; ++row)
for(int col=0; col<numCol; ++col)
if(data[row][col]!='x')
for(int dir=0; dir<4; ++dir){
auto const result=compute({dir, row, col});
(void) result;
/*
std::cerr<<row<<' '<<col<<' '<<dir<<'-'
<<result/numCol<<' '<<result%numCol<<'\n';
*/
}
int const numPos=numRow*numCol;
std::vector<int> distance_(numPos*numRobot*numRobot, INT_MAX);
auto const distance=[&](int a, int b, int pos)->int&{
assert(0<=a); assert(a<=b); assert(b<numRobot);
assert((unsigned)pos<unsigned(numPos));
return distance_[a+numRobot*(b+numRobot*pos)];
};
static_assert(sizeof(std::size_t)==4);
std::vector<std::vector<int>> queue(numPos*numRobot*7/4);
int result=INT_MAX;
for(int a=numRobot; a--;){
for(int b=a; b<numRobot; ++b){
struct State{
int pos, distance;
bool operator<(State it) const{return distance>it.distance;}
};
int minDistance=INT_MAX, maxDistance=0;
if(a==b){
//for(int pos=0; pos<numPos; ++pos)
for(int row=0; row<numRow; ++row)
for(int col=0; col<numCol; ++col){
assert(distance(a, a, Pos{row, col}.index())==INT_MAX);
if(data[row][col]==char('1'+a)){
auto const pos=Pos{row, col}.index();
queue[distance(a, a, pos)=0].push_back(pos);
minDistance=0;
}
}
}else{
for(int pos=0; pos<numPos; ++pos){
unsigned t=INT_MAX;
for(int m=a; m<b; ++m)
t=std::min(t, (unsigned)distance(a, m, pos)+
distance(m+1, b, pos));
assert(distance(a, b, pos)==INT_MAX);
if(t<INT_MAX){
if(b==numRobot-1 and a==0)
result=std::min(result, (int)t);
else{
queue[distance(a, b, pos)=t].push_back(pos);
minDistance=std::min(minDistance, (int)t);
maxDistance=std::max(maxDistance, (int)t);
}
}
}
}
for(int curDistance=minDistance; curDistance<=maxDistance; ++curDistance){
for(auto pos: queue[curDistance]){
if(curDistance!=distance(a, b, pos)) continue;
for(int dir=0; dir<4; ++dir){
auto const next=getMemory(pos, dir);
if(next!=loop and distance(a, b, next)>curDistance+1){
queue[distance(a, b, next)=curDistance+1].push_back(next);
maxDistance=std::max(maxDistance, curDistance+1);
}
}
}
}
}
}
std::cout<<(result==INT_MAX ? -1: result)<<'\n';
}
Compilation message
robots.cpp: In function 'int main()':
robots.cpp:99:35: error: static assertion failed
99 | static_assert(sizeof(std::size_t)==4);
| ~~~~~~~~~~~~~~~~~~~^~~
robots.cpp: In member function 'std::pair<int, int> State::dirVector() const':
robots.cpp:29:2: warning: control reaches end of non-void function [-Wreturn-type]
29 | }
| ^
