hdu1978 How many ways(DP)
#include<bits\stdc++.h>
using namespace std;
const int maxn = 105;
int mp[maxn][maxn];
int dp[maxn][maxn];
int n,m;
int check(int x,int y)
{
if(x<1||x>n||y<1||y>m)
return 1;
return 0;
}
int dfs(int x,int y)
{
if(dp[x][y]>=0 )
return dp[x][y];
dp[x][y]=0;
for (int i = 0;i<=mp[x][y];i++)
for (int j = 0;j<=mp[x][y]-i;j++)
{
if(check(x+i,y+j))
continue;
dp[x][y]=(dp[x][y]+dfs(x+i,y+j))%10000;
}
return dp[x][y];
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
// int n,m;
scanf("%d%d",&n,&m);
for (int i = 1;i<=n;i++)
for (int j = 1;j<=m;j++)
scanf("%d",&mp[i][j]);
memset(dp,-1,sizeof(dp));
dp[n][m]=1;
printf("%d
",dfs(1,1));
}
}
Description
이것은 간단한 생존 게임으로 로봇이 바둑판의 시작점(1,1)에서 바둑판의 종점(n,m)까지 가는 것을 제어한다.게임의 규칙은 다음과 같습니다.
1. 로봇은 처음에 바둑판의 시작점과 시작점에 표시된 에너지가 있다.
2. 로봇은 오른쪽이나 아래로 갈 수 있고 한 걸음 한 걸음 갈 때마다 에너지를 소모한다.
3. 로봇은 제자리에 머물 수 없다.
4. 로봇이 실행 가능한 경로를 선택한 후에 그가 이 경로의 종점에 도착했을 때 그는 종점에 표시된 에너지만 있을 것이다.
위의 그림에서 보듯이 로봇은 처음에 (1,1)점에 있고 4개의 에너지를 가지고 있다. 파란색 네모난 블록은 그가 도착할 수 있는 점을 나타낸다. 만약에 그가 이번 경로 선택에서 선택한 종점은(2,4)이다.
점, 그가 (2,4)점에 도달했을 때 1 단위의 에너지를 가지고 다음 경로 선택을 시작한다(6,6)점까지.
우리의 문제는 로봇이 기점에서 종점까지 몇 가지 방식을 가지고 있느냐는 것이다.이것은 아마도 매우 큰 숫자일 것이다. 출력의 결과는 10000에 대한 모형이다.
Input
첫 번째 행에는 데이터의 그룹 수를 나타내는 정수 T를 입력합니다.
각 그룹의 데이터 첫 줄에 두 개의 정수 n, m(1<=n, m<=100)을 입력한다.바둑판의 크기를 나타낸다.다음에 n 줄을 입력하고 각 줄마다 m 개의 정수 e(0 <=e < 20)를 입력합니다.
Output
각 그룹의 데이터 출력 방식에 대한 총 수량이 10000에 대한 추출 결과입니다.
Sample Input
1
6 6
4 5 6 6 4 3
2 2 3 1 7 2
1 1 4 6 2 7
5 8 4 3 9 5
7 6 6 2 1 5
3 1 1 3 7 2
Sample Output
3948
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
