제출 #262852

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
262852		user202729	로봇 (APIO13_robots)	C++17	60 / 100	1029 ms	163844 KiB

robots

// 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)];
	};

	std::vector<std::vector<int>> queue(numPos*numRobot*7/8+20);

	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';
}

컴파일 시 표준 에러 (stderr) 메시지

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 |  }
      |  ^

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