두니발 박사의 탈옥 :: 알고스팟

문제 : https://algospot.com/judge/problem/read/NUMB3RS

코드 ( C++ )

	#include <iostream>
	#include <algorithm>
	#include <vector>
	#include <cstring>
	#include <iomanip>
	using namespace std;
	int N, D, P, Q;
	int connected[51][51], deg[51];
	double cache[51][101];
	//connected[i][j] == 마을 i,j가 연결되어 있나 여부
	//deg[i] = 마을 i와 연결된 마을의 개수
	double solve(int here, int days)
	{
	// 기저 사례: 0 일째
	if (days == 0)
	return (here == P ? 1.0 : 0.0);
	//메모이제이션
	double &ret = cache[here][days];
	if (ret > -0.5)
	return ret;
	ret = 0.0;
	for (int there =0; there <N; ++there)
	{
	if (connected[here][there]) {
	ret += solve(there, days-1) / deg[there];
	}
	}
	return ret;
	}
	int main()
	{
	int C;
	cin >> C;
	while (C--)
	{
	memset(cache, -1, sizeof(cache));
	memset(connected, 0, sizeof(connected));
	memset(deg, 0, sizeof(deg));
	cin >> N >> D >> P;
	for (int i = 0; i < N; ++i)
	for (int j = 0; j < N; ++j) {
	cin >> connected[i][j];
	if (connected[i][j])
	deg[i]++;
	}
	int T;
	cin >> T;
	double ret = 0;
	while (T--)
	{
	double sum;
	int num;
	cin >> num;
	Q = P;
	sum = solve(num,D);
	cout << fixed << setprecision(8) << sum << "\n";
	}
	}
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub