BOJ 35000 The wheel to the right

문제 링크입니다.

문제 요약

직진 또는 우회전만 할 수 있는 말이 있습니다.

최단 경로가 $1\,300\,000$ 이상인 출발점과 도착점을 가진 $1\,000 \times 1\,000$ 격자를 구성하세요.

풀이

한 칸을 여러 번 지나도록 만드는 걸 목표로 합니다. 이를 위해, 최대한 많은 좌회전(P턴)을 일으킵니다.

두 P턴을 마주보게 배치해서 칸 하나를 아낄 수 있습니다. 이를 타일링하면 타일링 내부의 면적 당 최단 경로 상에서의 평균 길이가 $4/3$ 정도 나옵니다.

테두리를 비워놓고 P턴끼리 유일하게 연결될 수 있도록 잘 막아주면 $1\,300\,000$은 넉넉히 넘길 수 있습니다. 구체적인 구성 방식은 사진으로 대체합니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

char a[1234][1234];
const int N = 1000;

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	memset(a, '.', sizeof(a));
	
	for(int i = 3; i <= N-2; i++) for(int j = 3; j <= N-2; j++) if((i+j)%2 == 0 && abs(i-j)/2%2 == ((i+j+5)%12 < 6)) a[i][j] = '#';
	
	a[3][2] = 'F'; a[N-1][N] = 'S';
	for(int i = N-2; i >= 8; i -= 6) a[i][N] = a[i][N-1] = a[i-1][N-2] = a[i-3][N-2] = a[i-4][N-1] = a[i-4][N] = '#';
	for(int j = N-2; j >= 8; j -= 6) a[1][j] = a[2][j] = a[1][j-1] = a[2][j-1] = a[1][j-2] = a[2][j-2] = '#';
	a[1][1] = a[1][2] = a[2][1] = a[2][2] = a[3][1] = '#';
	for(int j = N-5; j >= 11; j -= 12) a[N-2][j+2] = a[N-2][j-4] = a[N-2][j] = a[N-2][j-1] = a[N-2][j-2] = a[N-2][j-6] = a[N-2][j-7] = a[N-2][j-8] = a[N][j] = a[N-1][j-6] = '#';
	a[N-1][2] = '#';
	for(int i = N-7; i >= 9; i -= 6) a[i][1] = a[i][2] = a[i-2][2] = a[i-3][2] = a[i-4][2] = '#';
	
	cout << N << ' ' << N << '\n';
	for(int i = 1; i <= N; i++, cout << '\n') for(int j = 1; j <= N; j++) cout << a[i][j];
}