Codeforces #802 : Div2 E. Serega the Pirate

コードが長め。
https://codeforces.com/contest/1700/problem/E

問題

1～H*Wの整数が1つずつ書かれた、H*Wのグリッドが与えられる。
初期状態で1のあるマスに駒があるとき、以下のように駒を動かせる。

• 隣接マスをたどりながら移動する。その差、今までx以下の整数の書かれたマスを通ったことがあるなら、(x+1)以下の書かれたマスに進入できる。

H*Wのあるマスまで移動可能にしたい。
任意の2マスの整数の入れ替えを行える時、最小何回行えば条件を達成できるか。
0・1・2以上のいずれか判定せよ。

解法

入れ替えを無視すると、全マスを移動できる条件は、1以外の各マスに、自身より小さい値の隣接マスが隣接することである。
もし移動不可なマスがある場合、解消するにはそのマスか隣接4マスのいずれかがSwap対象となることである。

0なら初期状態をチェックすればよい。
移動不可マスが1個あれば、5マスを他のH*Wマスと総当たりでSwapしてみればよい。

int H,W;
vector<int> A[404040];
int RY[404040],RX[404040];
int ok[404040];
int d[4]={0,1,0,-1};


int isng(int y,int x) {
	if(y<0||y>=H||x<0||x>=W) return 0;
	if(A[y][x]==0) return 0;
	int i;
	FOR(i,4) {
		int ty=y+d[i];
		int tx=x+d[i^1];
		if(ty>=0&&ty<H&&tx>=0&&tx<W&&A[ty][tx]<A[y][x]) return 0;
	}
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) {
		A[y].resize(W);
		FOR(x,W) {
			cin>>A[y][x];
			A[y][x]--;
			RY[A[y][x]]=y;
			RX[A[y][x]]=x;
		}
	}
	
	int mi=404040;
	int ng=0;
	FOR(y,H) FOR(x,W) {
		if(isng(y,x)) mi=min(mi,A[y][x]);
		ng+=isng(y,x);
	}
	
	if(ng==0) {
		cout<<0<<endl;
		return;
	}
	vector<pair<int,int>> S,T;
	FOR(y,H) FOR(x,W) S.push_back({y,x});
	T={{RY[mi],RX[mi]}};
	FOR(i,4) {
		int ty=RY[mi]+d[i];
		int tx=RX[mi]+d[i^1];
		if(ty>=0&&ty<H&&tx>=0&&tx<W) T.push_back({ty,tx});
	}
	int num=0;
	unordered_set<ll> did;
	vector<pair<int,int>> C;
	FORR(a,S) FORR(b,T) {
		ll ap=a.first*W+a.second;
		ll bp=b.first*W+b.second;
		C={a,b};
		if(did.count((bp<<30)+ap)) continue;
		did.insert((ap<<30)+bp);
		FOR(i,4) {
			int ty=a.first+d[i];
			int tx=a.second+d[i^1];
			if(ty>=0&&ty<H&&tx>=0&&tx<W) C.push_back({ty,tx});
		}
		FOR(i,4) {
			int ty=b.first+d[i];
			int tx=b.second+d[i^1];
			if(ty>=0&&ty<H&&tx>=0&&tx<W) C.push_back({ty,tx});
		}
		sort(ALL(C));
		C.erase(unique(ALL(C)),C.end());
		FORR2(y,x,C) ng-=isng(y,x);
		swap(A[a.first][a.second],A[b.first][b.second]);
		FORR2(y,x,C) ng+=isng(y,x);
		if(ng==0) num++;
		FORR2(y,x,C) ng-=isng(y,x);
		swap(A[a.first][a.second],A[b.first][b.second]);
		FORR2(y,x,C) ng+=isng(y,x);
	}
	
	if(num) {
		cout<<"1 "<<num<<endl;
	}
	else {
		cout<<2<<endl;
	}
	
	
}

まとめ

珍しい判定問題。