散歩する

11451 ワード
アルゴリズム#アルゴリズム# テキストリンク
白駿


1. Python

2. C++

#include<bits/stdc++.h>
using namespace std;

int A[1010][1010];
int dp[1010][1010];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int h, w, n; cin >> h >> w >> n;
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cin >> A[i][j];
		}
	}
	dp[1][1] = n - 1;
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			if (i > 1) dp[i][j] += (A[i - 1][j] == 0 ? (dp[i - 1][j] + 1) / 2 : dp[i - 1][j] / 2);
			if (j > 1) dp[i][j] += (A[i][j - 1] == 1 ? (dp[i][j - 1] + 1) / 2 : dp[i][j - 1] / 2);
		}
	}
	int x = 1, y = 1;
	while (x <= h && y <= w) {
		if ((A[x][y] + dp[x][y]) % 2) y++;
		else x++;
	}
	cout << x << ' ' << y << '\n';
}
 



출처: https://rebro.kr/142 [Rebro의 코딩 일기장]

  • 散策路を出ると散策は終わり、一度交差点を過ぎるとその交差点の方向が逆になります.つまり、右なら下、下なら右.

  • N-1回目の散歩終了後、N回目の散歩終了時の位置の問題.(N = 10^7)

  • 交差点の方向は交差点のアクセス回数に依存するので、N回目の散歩の前に、各交差点のアクセス回数を求めると、N回目の散歩の到着場所がわかります.
    したがって、dptableは
  • と定義される.
  • dp[i][j] = 교차로 (i, j)를 방문한 횟수が起点で、よく訪れるので(1, 1)です.
  • 現在の位置はdp[i][j] = N-1と呼ばれ、常に右または下に移動するため、(x, y)と(x-1, y)をチェックするだけでよい.
  • (x, y-1)の初期値が(x-1, y)0で(x-1, y)回アクセスしたと仮定する.では、kから(x-1, y)に移動します.
    逆に、
  • の初期値を(x, y)と呼ぶと、(k+1)/2から(x-1, y)に移動する.

  • すなわち,初期方向によって増加値が異なる.

  • 最終的には、N回目の散歩の前に交差点を作ってから、N回目に直接移動して、到着点を見つければいいのです.
    • make-コンパイル-リンクあれらの事
    [BaekJoon/Python]forゲート:11021、11022、2438、2439、10871