Codeforces #632 Div2 E. Road to 1600

余り解説することないな。
https://codeforces.com/contest/1333/problem/E

問題

N*Nのグリッドを考える。各セルには1～N*Nの値が1つずつ振られているとする。
最初1の値が振られたマスにチェスのコマを置こう。

以下、以下の通りの手順でコマを動かす。

• すでに全マス訪問済みなら終了。
• コマが1手で動かせる位置にあるマスのうち、未訪問でかつ最も小さい値のマスに移動する。
• そのようなマスがなければ、コストを1払い、未訪問のうち最も小さい値のマスに移動する。

コマとしてルークよりクイーンを使う方が全マス訪問のコストが高いケースを構築せよ。

解法

N≦2の場合解なし。
N=3の時は適当に総当たりなどで対応しよう。
N≧4の時は結局N=3の例に還元できる。

int N;
int A[501][501];

string S[3]={
	"124",
	"538",
	"967",
};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if(N<=2) return _P("-1\n");
	/*
	vector<int> V={1,2,3,4,5,6,7,8,9};
	do {
		FOR(i,9) A[i/3][i%3]=V[i];
		if(step1()>step2()) {
			
			cout<<step1()<<" "<<step2()<<endl;
			FOR(y,3) {
				FOR(x,3) cout<<A[y][x];
				cout<<endl;
			}
			cout<<endl;
		}
		
	} while(next_permutation(ALL(V)));
	return;
	*/
	int cur=1;
	for(i=N;i>=4;i--) {
		if(i%2==1) {
			FOR(x,i) A[N-i][x]=cur++;
			FOR(x,i-1) A[N-i+1+x][i-1]=cur++;
		}
		else {
			FOR(x,i-1) A[N-1-x][i-1]=cur++;
			FOR(x,i) A[N-i][i-1-x]=cur++;
		}
	}
	A[N-3][0]=cur++;
	A[N-3][1]=cur++;
	A[N-2][1]=cur++;
	A[N-3][2]=cur++;
	A[N-2][0]=cur++;
	A[N-1][1]=cur++;
	A[N-1][2]=cur++;
	A[N-2][2]=cur++;
	A[N-1][0]=cur++;
	
	FOR(y,N) {
		FOR(x,N) {
			_P("%d",A[y][x]);
			if(x!=N-1) _P(" ");
		}
		_P("\n");
	}
	
	
}

まとめ

本番割と苦労してた。