NC24015. [USACO 2016 Feb B]Cow Hopscotch
描述
Just like humans enjoy playing the game of Hopscotch, Farmer John's cows have invented a variant of the game for themselves to play. Being played by clumsy animals weighing nearly a ton, Cow Hopscotch almost always ends in disaster, but this has surprisingly not deterred the cows from attempting to play nearly every afternoon.
The game is played on an R by C grid (2 <= R <= 15, 2 <= C <= 15), where each square is colored either red or blue. Cows start in the top-left square and move to the bottom-right square by a sequence of jumps, where a jump is valid if and only if
1) You are jumping to a square of a different color,
2) The square that you are jumping to is at least one row below the current square that you are on, and
3) The square that you are jumping to is at least one column to the right of the current square that you are on.
Please help the cows compute the number of different possible sequences of valid jumps that will take them from the top-left square to the bottom-right square.
输入描述
The first line contains the two integers R and C. The next R lines will each contain C characters. Each character is either 'R' or a 'B', indicating a red square or a blue square.
输出描述
Output the number of different ways one can jump from the top-left square to the bottom-right square.
示例1
输入:
4 4 RRRR RRBR RBBR RRRR
输出:
3
C 解法, 执行用时: 7ms, 内存消耗: 384K, 提交时间: 2021-08-07 16:52:41
#include <stdio.h>
char a[15][16];
int r,c;
long long int sum=0;
void sum1(int h,int l)
{
if(h==r-1&&l==c-1) sum++;
for(int i=h+1;i<r;i++)
{
for(int j=l+1;j<c;j++)
{
if(a[i][j]!=a[h][l]) sum1(i,j);
}
}
}
int main()
{
scanf("%d %d",&r,&c);
for(int i=0;i<r;i++)
{
for(int j=0;j<c;j++) scanf(" %c",&a[i][j]);
}
sum1(0,0);
printf("%lld",sum);
return 0;
}
C++ 解法, 执行用时: 9ms, 内存消耗: 416K, 提交时间: 2022-07-02 11:43:21
#include<bits/stdc++.h>
using namespace std;
const int maxn = 20;
string s[maxn];
int R, C;
int solve(int x, int y){
if(x == R - 1 && y == C - 1) return 1;
int cnt = 0;
for(int i=x+1;i<R;++i)
for(int j=y+1;j<C;++j)
if(s[x][y] != s[i][j]) cnt += solve(i, j);
return cnt;
}
int main(){
cin>>R>>C;
for(int i=0;i<R;++i)cin>>s[i];
cout<<solve(0,0)<<endl;
return 0;
}
Python3(3.9) 解法, 执行用时: 24ms, 内存消耗: 2836K, 提交时间: 2021-01-02 11:38:29
s=input().split()
r=int(s[0])
c=int(s[1])
dp=[[0]*c for _ in range(r)]
strs=[]
for i in range(0,r):
strs.append(input())
dp[0][0]=1
for i in range(1,r):
for j in range(1,c):
for p in range(0,i):
for q in range(0,j):
if strs[p][q] != strs[i][j]:
dp[i][j]+=dp[p][q]
print(dp[r-1][c-1])