BOJ 1577-道路数

時間制限メモリ制限正解を提出正解正解正解正解正解率2秒16 MB 206052121216.933%

質問する

勢俊が生活している城市長は不思議だ.この町はメッシュ状で矩形です.都市の横方向の大きさはNで,縦方向の大きさはMである.また、勢俊の家は(0,0)、勢俊の学校は(N,M).
そのため、下図のように成長しています.

勢俊は家から学校までの道にいくつかの状況があることを知り始めた.
勢俊はいつも最短の道を行くので、いつも正確にN+Mの道を通ります.しかし、最近この町の道路はおから工事の疑いで工事中.道路は工事中、この道路を通ってはいけません.
(0,0)から(N,M)への異なるパスについては、個数を求めるプログラムを作成します.

入力

第1行は、道路の横方向サイズNおよび縦方向サイズMを与える.NとMは100以下の自然数であり、2行目は工事中の道路の個数Kを与える.Kは0以上、100以下の自然数である.3行目からK行目では,a b c dのような施工中の道路の情報が与えられる.aおよびcは0以上、N以下、bおよびdは0以上、M以下である.また,(a,b)と(c,d)の距離は常に1である.

しゅつりょく

最初の行が(0,0)~(N,M)の場合、数値が出力されます.この値は0以上、2^63-1以下の自然数です.

に近づく

table[i][j]=table[i-1][j]+table[i][j-1]は非常に簡単なDP問題です.
しかし、肝心なのは工事中の道路をどのように表現するかです.
座標ごとに2つの値の配列を作成します.
最初のインデックスが垂直線に接続されているかどうか.
2番目のインデックスを右横線が接続されているかどうかを指定します.
この配列を利用すると,例外処理を容易に行うことができる.

に答える

最初は横に見て、縦に見ていたので、逆入力されました.
a,b,c,dが入力されると、(a,b)はより小さな座標に変換される.
そしてa=cで横線か縦線かを確認します.
あとは順番に点火式を記入すればいいです.
端点値の異常処理に注意するだけです.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

ll N, M, K, arr[101][101][2], dp[101][101];


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

	MS(dp, 0);
	MS(arr, 0);
	CIN3(M, N, K);
	while (K--)
	{
		int a, b, c, d;
		CIN2(b, a);
		CIN2(d, c);
		if (a > c) swap(a, c);
		if (b > d) swap(b, d);
		arr[a][b][a == c] = 1; // 가로 1, 세로 0
	}
	dp[0][0] = 1;
	FUP(i, 0, N)
	{
		FUP(j, 0, M)
		{
			if (j != M && !arr[i][j][1]) dp[i][j + 1] += dp[i][j];
			if (i != N && !arr[i][j][0]) dp[i + 1][j] += dp[i][j];
		}
	}
	COUT(dp[N][M]);

	return 0;
}

おしゃべり

ショートコード1位