[白俊14890号]傾斜C++

[14890号スロープ]
https://www.acmicpc.net/problem/14890
この問題の核心は、1本の道(行や列)を歩くときに、1万のあごを上下できるかどうかだ.
time complexity: O(N^2)
space complexity: O(N^2)

解答方法

1.

moveRight()メソッドを作成し、rowを1～Nに回転させ、moveRight()が最後まで行けるかどうかを判断します.
moveDown()メソッドを作成し、columnを1~Nに回転させ、moveDown()が最後まで行けるかどうかを判断します.

2.

move**()メソッドは,前進可能か否かを判断する3つのケースに分けられる.

1.次のブロックの値が私が立っているブロックの値より大きい場合

a)
ブロック値の差が1を超えると上昇せず、0を返します.
b)
差が1の場合、これまでに数えたブロック数がL値以上の場合(すなわち、十分なブロックがある場合)、私の位置を次のブロック(すなわち、上方向)に移動し、これまで数えたブロック数を1にリセットします(移動位置に斜線が設定されていないため、ブロックが確保されています).
ブロック数が足りない場合は0を返します.

2.次のブロックの値が私が立っているブロックの値より小さい場合

a)
残りのブロック数がLより小さい場合(スロープを配置するのに十分なブロックがない場合)、0を返します.
b)
「私の位置」の次のblockからL個のblockに進み、blockの値がすべて(私のblock値)-1でない場合は0(長さLの斜面を置くblockの高さは同じでなければならないため)を返します.
c)
ブロックの値がすべて(私のブロック値)-1に等しい場合、私の位置を傾きの終わりに移動し、jまたはiの値を(jまたはi)+L-1に更新します.
(文の特性により、++j/+iが実行され、値は自然に(jまたはi)+Lに増加する)
この更新により、勾配終了地点である次の地点から比較を再開することができます(私の位置が勾配終了地点であることを忘れないでください).
これまでセンサブロックの個数は0に初期化されていた(私が移動した位置はスロープの終点なのでスロープを置くことができるブロックではない).

3.もし価格が同じなら、今までに1ブロック増やして私の位置に進みます。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>  // pair
#include <tuple>
#include <stack>
#define ll long long
#define INF 1e9
using namespace std;

int ans = 0;
int N;
int map[101][101];
int L;

int moveRight(int &r, int &c) {
	int cnt = 1;
	int val = map[r][c]; // the value of my block

	for(int j=c+1;j<=N;++j) {
		// the next block bigger
		if(map[r][j] > val) {
			if(map[r][j] != val + 1) {
				return 0;
			}

			if(cnt >= L) {
				val = map[r][j];
				cnt = 1;
			} else {
				return 0;
			}
		}
		// the next block smaller
		else if(map[r][j] < val) {
			if(N - j + 1 < L) {  // minimum length not enough
				return 0;
			}

			for(int k=j;k<=j+L-1;++k) {
				if(map[r][k] != val - 1) {
					return 0;
				}
			}

			val = map[r][j+L-1];
			j = j + L - 1;
			cnt = 0;
		}
		// the same
		else {
			cnt++;
			val = map[r][j];
		}
	}

	return 1;
}

int moveDown(int &r, int &c) {
	int cnt = 1;
	int val = map[r][c];

	for(int i=r+1;i<=N;++i) {
		if(map[i][c] > val) {
			if(map[i][c] != val + 1) {
				return 0;
			}

			if(cnt >= L) {
				val = map[i][c];
				cnt = 1;
			} else {
				return 0;
			}
		} else if(map[i][c] < val) {
			if(N - i + 1 < L) {
				return 0;
			}
			for(int k=i;k<=i+L-1;++k) {
				if(map[k][c] != val - 1) {
					return 0;
				}
			}
			val = map[i+L-1][c];
			i = i + L - 1;
			cnt = 0;
		} else {
			cnt++;
			val = map[i][c];
		}
	}

	return 1;
}

void sol() {
	for(int i=1;i<=N;++i) {
		int c = 1;
		if(moveRight(i,c)) {
			ans++;
		}
	}

	for(int j=1;j<=N;++j) {
		int r = 1;
		if(moveDown(r,j)) {
			ans++;
		}
	}
}

int main(void) {
	ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

	cin >> N >> L;
	for(int i=1;i<=N;++i) {
		for(int j=1;j<=N;++j) {
			cin >> map[i][j];
		}
	}
	
	sol();

	cout << ans << '\n';
	
	return 0;
}