2023-06-30：給你一個 rows * cols 大小的矩形披薩和一個整數(shù) k，

矩形包含兩種字符： 'A' （表示蘋果）和 '.' （表示空白格子），

你需要切披薩 k-1 次，得到 k 塊披薩并送給別人，

切披薩的每一刀，先要選擇是向垂直還是水平方向切，再在矩形的邊界上選一個切的位置，

將披薩一分為二。如果垂直地切披薩，那么需要把左邊的部分送給一個人，

如果水平地切，那么需要把上面的部分送給一個人，

在切完最后一刀后，需要把剩下來的一塊送給最后一個人。

請你返回確保每一塊披薩包含 至少 一個蘋果的切披薩方案數(shù)。

由于答案可能是個很大的數(shù)字，請你返回它對 10^9 + 7 取余的結(jié)果。

輸入：pizza = ["A..","AAA","..."], k = 3。

輸出：3。

答案2023-06-30：

大體過程如下：

算法1：遞歸法

1.定義常量 mod = 1000000007。

2.定義函數(shù) ways1(pizza []string, k int) int，接收一個披薩矩形和切割次數(shù) k，返回方案數(shù)。

3.獲取披薩的行數(shù) n 和列數(shù) m。

4.創(chuàng)建一個二維數(shù)組 sum，用于記錄每個位置左上角區(qū)域內(nèi)的蘋果數(shù)量的累加和。

5.調(diào)用函數(shù) setAppleMatrix，計算 sum 數(shù)組。

6.調(diào)用函數(shù) process，傳入 sum、n、m、初始行、初始列和切割次數(shù) k。

7.在函數(shù) process 中，首先判斷當(dāng)前切割位置的左上角區(qū)域內(nèi)是否包含蘋果，若不包含則返回 0。

8.若切割次數(shù) rest 等于 1，表示只需要切割一次，直接返回 1。

9.初始化變量 ways 為 0，表示方案數(shù)。

10.在列方向上進行切割，遍歷從當(dāng)前切割位置 col 開始到第 m 列的所有位置。

10.1.若從當(dāng)前切割位置到當(dāng)前列的左上角區(qū)域內(nèi)包含蘋果，則遞歸調(diào)用 process 函數(shù)，切割位置更新為 i+1，切割次數(shù)更新為 rest-1，得到的方案數(shù)累加到 ways 中，并對 ways 取模。

11.在行方向上進行切割，遍歷從當(dāng)前切割位置 row 開始到第 n 行的所有位置。

11.1.若從當(dāng)前切割位置到當(dāng)前行的左上角區(qū)域內(nèi)包含蘋果，則遞歸調(diào)用 process 函數(shù)，切割位置更新為 i+1，切割次數(shù)更新為 rest-1，得到的方案數(shù)累加到 ways 中，并對 ways 取模。

12.返回 ways。

算法2：動態(tài)規(guī)劃法

1.定義常量 mod = 1000000007。

2.定義函數(shù) ways2(pizza []string, k int) int，接收一個披薩矩形和切割次數(shù) k，返回方案數(shù)。

3.獲取披薩的行數(shù) n 和列數(shù) m。

4.創(chuàng)建一個二維數(shù)組 sum，用于記錄每個位置左上角區(qū)域內(nèi)的蘋果數(shù)量的累加和。

5.調(diào)用函數(shù) setAppleMatrix，計算 sum 數(shù)組。

6.創(chuàng)建一個三維動態(tài)規(guī)劃數(shù)組 dp，大小為 k+1 * (n+1) * (m+1)，用于記錄切割方案數(shù)。

7.初始化 dp 數(shù)組的第一層，即切割次數(shù)為 1 的情況。遍歷披薩的所有位置 (r, c)：

7.1.若從當(dāng)前切割位置到當(dāng)前位置的左上角區(qū)域內(nèi)包含蘋果，則 dp[1][r][c] = 1。

8.從切割次數(shù)為 2 開始，逐層計算 dp 數(shù)組，直到切割次數(shù)為 k。

9.在每一層 level 中，遍歷披薩的所有位置 (row, col)，從最后一行和最后一列開始更新 dp 值：

9.1.初始化變量 ways 為 0，表示方案數(shù)。

9.2.在列方向上進行切割，遍歷從當(dāng)前切割位置 col 開始到第 m 列的所有位置 c。

9.2.1.若從當(dāng)前切割位置到當(dāng)前列的左上角區(qū)域內(nèi)包含蘋果，則遍歷切割位置 c+1 到 m 的所有位置 s：

9.2.1.1.將 dp[level-1][row][s] 的方案數(shù)累加到 ways 中，并對 ways 取模。

9.2.1.2.當(dāng)遇到包含蘋果的位置時，跳出循環(huán)。

9.3.在行方向上進行切割，遍歷從當(dāng)前切割位置 row 開始到第 n 行的所有位置 r。

9.3.1.若從當(dāng)前切割位置到當(dāng)前行的左上角區(qū)域內(nèi)包含蘋果，則遍歷切割位置 r+1 到 n 的所有位置 s：

9.3.1.1.將 dp[level-1][s][col] 的方案數(shù)累加到 ways 中，并對 ways 取模。

9.3.1.2.當(dāng)遇到包含蘋果的位置時，跳出循環(huán)。

9.4.將 ways 賦值給 dp[level][row][col]。

10.返回 dp[k][1][1]。

算法1：

• ??時間復(fù)雜度：O(n^2 * m^2 * k)

• ??空間復(fù)雜度：O(n * m)

算法2：

• ??時間復(fù)雜度：O(n^2 * m^2 * k)

• ??空間復(fù)雜度：O(k * n * m)

在這兩種算法中，n 是披薩的行數(shù)，m 是披薩的列數(shù)，k 是需要切割披薩的次數(shù)。它們具有相同的時間和空間復(fù)雜度，因為它們都采用了類似的動態(tài)規(guī)劃方法來計算切割披薩的方式數(shù)量。

注意：通過使用前綴和在常數(shù)時間內(nèi)計算給定子矩陣中蘋果數(shù)量，可以進一步優(yōu)化時間復(fù)雜性，而不是使用apple()函數(shù)，但總體復(fù)雜性保持不變。

go完整代碼如下：

package?main

import?(
????"fmt"
)

const?mod?=?1000000007

func?ways1(pizza?[]string,?k?int)?int?{
????n?:=?len(pizza)
????m?:=?len(pizza[0])
????sum?:=?make([][]int,?n+1)
????for?i?:=?0;?i?<=?n;?i++?{
????????sum[i]?=?make([]int,?m+1)
????}
????setAppleMatrix(pizza,?sum,?n,?m)
????return?process(sum,?n,?m,?1,?1,?k)
}

func?process(sum?[][]int,?n,?m,?row,?col,?rest?int)?int?{
????if?apple(sum,?row,?col,?n,?m)?==?0?{
????????return?0
????}
????if?rest?==?1?{
????????return?1
????}
????ways?:=?0
????for?i?:=?col;?i?<?m;?i++?{
????????if?apple(sum,?row,?col,?n,?i)?>?0?{
????????????ways?+=?process(sum,?n,?m,?row,?i+1,?rest-1)
????????????ways?%=?mod
????????}
????}
????for?i?:=?row;?i?<?n;?i++?{
????????if?apple(sum,?row,?col,?i,?m)?>?0?{
????????????ways?+=?process(sum,?n,?m,?i+1,?col,?rest-1)
????????????ways?%=?mod
????????}
????}
????return?ways
}

func?ways2(pizza?[]string,?k?int)?int?{
????n?:=?len(pizza)
????m?:=?len(pizza[0])
????sum?:=?make([][]int,?n+1)
????for?i?:=?0;?i?<=?n;?i++?{
????????sum[i]?=?make([]int,?m+1)
????}
????setAppleMatrix(pizza,?sum,?n,?m)
????dp?:=?make([][][]int,?k+1)
????for?i?:=?0;?i?<=?k;?i++?{
????????dp[i]?=?make([][]int,?n+1)
????????for?j?:=?0;?j?<=?n;?j++?{
????????????dp[i][j]?=?make([]int,?m+1)
????????}
????}

????for?r?:=?1;?r?<=?n;?r++?{
????????for?c?:=?1;?c?<=?m;?c++?{
????????????if?apple(sum,?r,?c,?n,?m)?>?0?{
????????????????dp[1][r][c]?=?1
????????????}
????????}
????}

????for?level?:=?2;?level?<=?k;?level++?{
????????for?row?:=?n;?row?>=?1;?row--?{
????????????for?col?:=?m;?col?>=?1;?col--?{
????????????????ways?:=?0
????????????????for?c?:=?col;?c?<?m;?c++?{
????????????????????if?apple(sum,?row,?col,?n,?c)?>?0?{
????????????????????????for?s?:=?c?+?1;?s?<=?m;?s++?{
????????????????????????????ways?+=?dp[level-1][row][s]
????????????????????????????ways?%=?mod
????????????????????????}
????????????????????????break
????????????????????}
????????????????}
????????????????for?r?:=?row;?r?<?n;?r++?{
????????????????????if?apple(sum,?row,?col,?r,?m)?>?0?{
????????????????????????for?s?:=?r?+?1;?s?<=?n;?s++?{
????????????????????????????ways?+=?dp[level-1][s][col]
????????????????????????????ways?%=?mod
????????????????????????}
????????????????????????break
????????????????????}
????????????????}
????????????????dp[level][row][col]?=?ways
????????????}
????????}
????}
????return?dp[k][1][1]
}

func?setAppleMatrix(pizza?[]string,?sum?[][]int,?n,?m?int)?{
????for?i?:=?0;?i?<?n;?i++?{
????????for?j?:=?0;?j?<?m;?j++?{
????????????if?pizza[i][j]?==?'A'?{
????????????????sum[i+1][j+1]?=?1
????????????}
????????}
????}
????for?i?:=?1;?i?<=?n;?i++?{
????????for?j?:=?1;?j?<=?m;?j++?{
????????????sum[i][j]?+=?sum[i-1][j]?+?sum[i][j-1]?-?sum[i-1][j-1]
????????}
????}
}

func?apple(sum?[][]int,?a,?b,?c,?d?int)?int?{
????return?sum[c][d]?-?sum[c][b-1]?-?sum[a-1][d]?+?sum[a-1][b-1]
}

func?main()?{
????pizza?:=?[]string{"A..",?"AAA",?"..."}
????k?:=?3

????fmt.Println(ways1(pizza,?k))
????fmt.Println(ways2(pizza,?k))
}

rust完整代碼如下：

const?MOD:?i32?=?1_000_000_007;

fn?ways1(pizza:?Vec<String>,?k:?i32)?->?i32?{
????let?n?=?pizza.len();
????let?m?=?pizza[0].len();
????let?mut?sum?=?vec![vec![0;?m?+?1];?n?+?1];
????set_apple_matrix(&pizza,?&mut?sum,?n,?m);
????process(&sum,?n,?m,?1,?1,?k)
}

fn?process(sum:?&Vec<Vec<i32>>,?n:?usize,?m:?usize,?row:?usize,?col:?usize,?rest:?i32)?->?i32?{
????if?apple(sum,?row,?col,?n,?m)?==?0?{
????????return?0;
????}
????if?rest?==?1?{
????????return?1;
????}
????let?mut?ways?=?0;
????for?i?in?col..m?{
????????if?apple(sum,?row,?col,?n,?i)?>?0?{
????????????ways?+=?process(sum,?n,?m,?row,?i?+?1,?rest?-?1);
????????????ways?%=?MOD;
????????}
????}
????for?i?in?row..n?{
????????if?apple(sum,?row,?col,?i,?m)?>?0?{
????????????ways?+=?process(sum,?n,?m,?i?+?1,?col,?rest?-?1);
????????????ways?%=?MOD;
????????}
????}
????ways
}

fn?ways2(pizza:?Vec<String>,?k:?i32)?->?i32?{
????let?n?=?pizza.len();
????let?m?=?pizza[0].len();
????let?mut?sum?=?vec![vec![0;?m?+?1];?n?+?1];
????set_apple_matrix(&pizza,?&mut?sum,?n,?m);
????let?mut?dp?=?vec![vec![vec![0;?m?+?1];?n?+?1];?k?as?usize?+?1];
????for?r?in?1..=n?{
????????for?c?in?1..=m?{
????????????if?apple(&sum,?r,?c,?n,?m)?>?0?{
????????????????dp[1][r][c]?=?1;
????????????}
????????}
????}
????for?level?in?2..=k?as?usize?{
????????for?row?in?(1..=n).rev()?{
????????????for?col?in?(1..=m).rev()?{
????????????????let?mut?ways?=?0;
????????????????for?c?in?col..m?{
????????????????????if?apple(&sum,?row,?col,?n,?c)?>?0?{
????????????????????????for?s?in?c?+?1..=m?{
????????????????????????????ways?+=?dp[level?-?1][row][s];
????????????????????????????ways?%=?MOD;
????????????????????????}
????????????????????????break;
????????????????????}
????????????????}
????????????????for?r?in?row..n?{
????????????????????if?apple(&sum,?row,?col,?r,?m)?>?0?{
????????????????????????for?s?in?r?+?1..=n?{
????????????????????????????ways?+=?dp[level?-?1][s][col];
????????????????????????????ways?%=?MOD;
????????????????????????}
????????????????????????break;
????????????????????}
????????????????}
????????????????dp[level][row][col]?=?ways;
????????????}
????????}
????}
????dp[k?as?usize][1][1]
}

fn?set_apple_matrix(pizza:?&Vec<String>,?sum:?&mut?Vec<Vec<i32>>,?n:?usize,?m:?usize)?{
????for?i?in?0..n?{
????????let?row?=?pizza[i].chars().collect::<Vec<char>>();
????????for?j?in?0..m?{
????????????sum[i?+?1][j?+?1]?=?if?row[j]?==?'A'?{?1?}?else?{?0?};
????????}
????}
????for?i?in?1..=n?{
????????for?j?in?1..=m?{
????????????sum[i][j]?+=?sum[i?-?1][j]?+?sum[i][j?-?1]?-?sum[i?-?1][j?-?1];
????????}
????}
}

fn?apple(sum:?&Vec<Vec<i32>>,?a:?usize,?b:?usize,?c:?usize,?d:?usize)?->?i32?{
????sum[c][d]?-?sum[c][b?-?1]?-?sum[a?-?1][d]?+?sum[a?-?1][b?-?1]
}

fn?main()?{
????let?pizza?=?vec![
????????String::from("A.."),
????????String::from("AAA"),
????????String::from("...")
????];
????let?k?=?3;
????let?res1?=?ways1(pizza.clone(),?k);
????let?res2?=?ways2(pizza,?k);
????println!("Result?1:?{}",?res1);
????println!("Result?2:?{}",?res2);
}

c++完整代碼如下：

#include?<iostream>
#include?<vector>
using?namespace?std;

const?int?mod?=?1000000007;

void?setAppleMatrix(vector<string>&?pizza,?vector<vector<int>>&?sum,?int?n,?int?m)?{
????for?(int?i?=?0;?i?<?n;?i++)?{
????????for?(int?j?=?0;?j?<?m;?j++)?{
????????????sum[i?+?1][j?+?1]?=?(pizza[i][j]?==?'A')???1?:?0;
????????}
????}
????for?(int?i?=?1;?i?<=?n;?i++)?{
????????for?(int?j?=?1;?j?<=?m;?j++)?{
????????????sum[i][j]?+=?sum[i?-?1][j]?+?sum[i][j?-?1]?-?sum[i?-?1][j?-?1];
????????}
????}
}

int?apple(vector<vector<int>>&?sum,?int?a,?int?b,?int?c,?int?d)?{
????return?sum[c][d]?-?sum[c][b?-?1]?-?sum[a?-?1][d]?+?sum[a?-?1][b?-?1];
}

void?setNear(vector<vector<int>>&?sum,?vector<vector<int>>&?nearr,?vector<vector<int>>&?nearc,?int?n,?int?m)?{
????for?(int?r?=?1;?r?<=?n;?r++)?{
????????int?right?=?m?+?1;
????????int?number?=?0;
????????for?(int?c?=?m;?c?>=?1;?c--)?{
????????????int?curApple?=?apple(sum,?r,?c,?n,?m);
????????????if?(curApple?>?number)?{
????????????????number?=?curApple;
????????????????right?=?c;
????????????}
????????????nearc[r][c]?=?right;
????????}
????}
????for?(int?c?=?1;?c?<=?m;?c++)?{
????????int?down?=?n?+?1;
????????int?number?=?0;
????????for?(int?r?=?n;?r?>=?1;?r--)?{
????????????int?curApple?=?apple(sum,?r,?c,?n,?m);
????????????if?(curApple?>?number)?{
????????????????number?=?curApple;
????????????????down?=?r;
????????????}
????????????nearr[r][c]?=?down;
????????}
????}
}

void?setRowColSums(vector<vector<int>>&?dp,?vector<vector<int>>&?rs,?vector<vector<int>>&?cs,?int?n,?int?m)?{
????rs[n][m]?=?dp[n][m];
????cs[n][m]?=?dp[n][m];
????for?(int?r?=?n?-?1;?r?>=?1;?r--)?{
????????cs[r][m]?=?dp[r][m];
????????rs[r][m]?=?(dp[r][m]?+?rs[r?+?1][m])?%?mod;
????}
????for?(int?c?=?m?-?1;?c?>=?1;?c--)?{
????????rs[n][c]?=?dp[n][c];
????????cs[n][c]?=?(dp[n][c]?+?cs[n][c?+?1])?%?mod;
????}
????for?(int?r?=?n?-?1;?r?>=?1;?r--)?{
????????for?(int?c?=?m?-?1;?c?>=?1;?c--)?{
????????????rs[r][c]?=?(dp[r][c]?+?rs[r?+?1][c])?%?mod;
????????????cs[r][c]?=?(dp[r][c]?+?cs[r][c?+?1])?%?mod;
????????}
????}
}

int?process(vector<vector<int>>&?sum,?int?n,?int?m,?int?row,?int?col,?int?rest);

int?ways1(vector<string>&?pizza,?int?k)?{
????int?n?=?pizza.size();
????int?m?=?pizza[0].length();
????vector<vector<int>>?sum(n?+?1,?vector<int>(m?+?1));
????setAppleMatrix(pizza,?sum,?n,?m);

????return?process(sum,?n,?m,?1,?1,?k);
}

int?process(vector<vector<int>>&?sum,?int?n,?int?m,?int?row,?int?col,?int?rest)?{
????if?(apple(sum,?row,?col,?n,?m)?==?0)?{
????????return?0;
????}
????if?(rest?==?1)?{
????????return?1;
????}
????int?ways?=?0;
????for?(int?i?=?col;?i?<?m;?i++)?{
????????if?(apple(sum,?row,?col,?n,?i)?>?0)?{
????????????ways?+=?process(sum,?n,?m,?row,?i?+?1,?rest?-?1);
????????????ways?%=?mod;
????????}
????}
????for?(int?i?=?row;?i?<?n;?i++)?{
????????if?(apple(sum,?row,?col,?i,?m)?>?0)?{
????????????ways?+=?process(sum,?n,?m,?i?+?1,?col,?rest?-?1);
????????????ways?%=?mod;
????????}
????}
????return?ways;
}

int?ways2(vector<string>&?pizza,?int?k)?{
????int?n?=?pizza.size();
????int?m?=?pizza[0].length();
????vector<vector<int>>?sum(n?+?1,?vector<int>(m?+?1));
????setAppleMatrix(pizza,?sum,?n,?m);
????vector<vector<vector<int>>>?dp(k?+?1,?vector<vector<int>>(n?+?1,?vector<int>(m?+?1)));
????for?(int?r?=?1;?r?<=?n;?r++)?{
????????for?(int?c?=?1;?c?<=?m;?c++)?{
????????????if?(apple(sum,?r,?c,?n,?m)?>?0)?{
????????????????dp[1][r][c]?=?1;
????????????}
????????}
????}
????for?(int?level?=?2;?level?<=?k;?level++)?{
????????for?(int?row?=?n;?row?>=?1;?row--)?{
????????????for?(int?col?=?m;?col?>=?1;?col--)?{
????????????????int?ways?=?0;
????????????????for?(int?c?=?col;?c?<?m;?c++)?{
????????????????????if?(apple(sum,?row,?col,?n,?c)?>?0)?{
????????????????????????for?(int?s?=?c?+?1;?s?<=?m;?s++)?{
????????????????????????????ways?+=?dp[level?-?1][row][s];
????????????????????????????ways?%=?mod;
????????????????????????}
????????????????????????break;
????????????????????}
????????????????}
????????????????for?(int?r?=?row;?r?<?n;?r++)?{
????????????????????if?(apple(sum,?row,?col,?r,?m)?>?0)?{
????????????????????????for?(int?s?=?r?+?1;?s?<=?n;?s++)?{
????????????????????????????ways?+=?dp[level?-?1][s][col];
????????????????????????????ways?%=?mod;
????????????????????????}
????????????????????????break;
????????????????????}
????????????????}
????????????????dp[level][row][col]?=?ways;
????????????}
????????}
????}
????return?dp[k][1][1];
}

int?main()?{
????vector<string>?pizza?=?{?"A..",?"AAA",?"..."?};
????int?k?=?3;

????int?result1?=?ways1(pizza,?k);
????int?result2?=?ways2(pizza,?k);

????cout?<<?"Result?1:?"?<<?result1?<<?endl;
????cout?<<?"Result?2:?"?<<?result2?<<?endl;

????return?0;
}

c完整代碼如下：

#include?<stdio.h>
#include?<stdlib.h>
#include?<string.h>

#define?mod?1000000007

void?setAppleMatrix(char**?pizza,?int**?sum,?int?n,?int?m)?{
????for?(int?i?=?0;?i?<?n;?i++)?{
????????for?(int?j?=?0;?j?<?m;?j++)?{
????????????sum[i?+?1][j?+?1]?=?(pizza[i][j]?==?'A'???1?:?0);
????????}
????}
????for?(int?i?=?1;?i?<=?n;?i++)?{
????????for?(int?j?=?1;?j?<=?m;?j++)?{
????????????sum[i][j]?+=?sum[i?-?1][j]?+?sum[i][j?-?1]?-?sum[i?-?1][j?-?1];
????????}
????}
}

int?apple(int**?sum,?int?a,?int?b,?int?c,?int?d)?{
????return?sum[c][d]?-?sum[c][b?-?1]?-?sum[a?-?1][d]?+?sum[a?-?1][b?-?1];
}

void?setNear(int**?sum,?int**?nearr,?int**?nearc,?int?n,?int?m)?{
????for?(int?r?=?1;?r?<=?n;?r++)?{
????????int?right?=?m?+?1;
????????int?number?=?0;
????????for?(int?c?=?m;?c?>=?1;?c--)?{
????????????int?curApple?=?apple(sum,?r,?c,?n,?m);
????????????if?(curApple?>?number)?{
????????????????number?=?curApple;
????????????????right?=?c;
????????????}
????????????nearc[r][c]?=?right;
????????}
????}
????for?(int?c?=?1;?c?<=?m;?c++)?{
????????int?down?=?n?+?1;
????????int?number?=?0;
????????for?(int?r?=?n;?r?>=?1;?r--)?{
????????????int?curApple?=?apple(sum,?r,?c,?n,?m);
????????????if?(curApple?>?number)?{
????????????????number?=?curApple;
????????????????down?=?r;
????????????}
????????????nearr[r][c]?=?down;
????????}
????}
}

void?setRowColSums(int**?dp,?int**?rs,?int**?cs,?int?n,?int?m)?{
????rs[n][m]?=?dp[n][m];
????cs[n][m]?=?dp[n][m];
????for?(int?r?=?n?-?1;?r?>=?1;?r--)?{
????????cs[r][m]?=?dp[r][m];
????????rs[r][m]?=?(dp[r][m]?+?rs[r?+?1][m])?%?mod;
????}
????for?(int?c?=?m?-?1;?c?>=?1;?c--)?{
????????rs[n][c]?=?dp[n][c];
????????cs[n][c]?=?(dp[n][c]?+?cs[n][c?+?1])?%?mod;
????}
????for?(int?r?=?n?-?1;?r?>=?1;?r--)?{
????????for?(int?c?=?m?-?1;?c?>=?1;?c--)?{
????????????rs[r][c]?=?(dp[r][c]?+?rs[r?+?1][c])?%?mod;
????????????cs[r][c]?=?(dp[r][c]?+?cs[r][c?+?1])?%?mod;
????????}
????}
}

int?ways1(char**?pizza,?int?pizzaSize,?int?k)?{
????int?n?=?pizzaSize;
????int?m?=?strlen(pizza[0]);
????int**?sum?=?(int**)malloc((n?+?1)?*?sizeof(int*));
????for?(int?i?=?0;?i?<=?n;?i++)?{
????????sum[i]?=?(int*)calloc(m?+?1,?sizeof(int));
????}
????setAppleMatrix(pizza,?sum,?n,?m);
????int?result?=?process(sum,?n,?m,?1,?1,?k);
????for?(int?i?=?0;?i?<=?n;?i++)?{
????????free(sum[i]);
????}
????free(sum);
????return?result;
}

int?process(int**?sum,?int?n,?int?m,?int?row,?int?col,?int?rest)?{
????if?(apple(sum,?row,?col,?n,?m)?==?0)?{
????????return?0;
????}
????if?(rest?==?1)?{
????????return?1;
????}
????int?ways?=?0;
????for?(int?i?=?col;?i?<?m;?i++)?{
????????if?(apple(sum,?row,?col,?n,?i)?>?0)?{
????????????ways?+=?process(sum,?n,?m,?row,?i?+?1,?rest?-?1);
????????????ways?%=?mod;
????????}
????}
????for?(int?i?=?row;?i?<?n;?i++)?{
????????if?(apple(sum,?row,?col,?i,?m)?>?0)?{
????????????ways?+=?process(sum,?n,?m,?i?+?1,?col,?rest?-?1);
????????????ways?%=?mod;
????????}
????}
????return?ways;
}

int?ways2(char**?pizza,?int?pizzaSize,?int?k)?{
????int?n?=?pizzaSize;
????int?m?=?strlen(pizza[0]);
????int**?sum?=?(int**)malloc((n?+?1)?*?sizeof(int*));
????for?(int?i?=?0;?i?<=?n;?i++)?{
????????sum[i]?=?(int*)calloc(m?+?1,?sizeof(int));
????}
????setAppleMatrix(pizza,?sum,?n,?m);
????int***?dp?=?(int***)malloc((k?+?1)?*?sizeof(int**));
????for?(int?i?=?0;?i?<=?k;?i++)?{
????????dp[i]?=?(int**)malloc((n?+?1)?*?sizeof(int*));
????????for?(int?j?=?0;?j?<=?n;?j++)?{
????????????dp[i][j]?=?(int*)calloc(m?+?1,?sizeof(int));
????????}
????}
????for?(int?r?=?1;?r?<=?n;?r++)?{
????????for?(int?c?=?1;?c?<=?m;?c++)?{
????????????if?(apple(sum,?r,?c,?n,?m)?>?0)?{
????????????????dp[1][r][c]?=?1;
????????????}
????????}
????}
????int?result?=?0;
????for?(int?level?=?2;?level?<=?k;?level++)?{
????????for?(int?row?=?n;?row?>=?1;?row--)?{
????????????for?(int?col?=?m;?col?>=?1;?col--)?{
????????????????int?ways?=?0;
????????????????for?(int?c?=?col;?c?<?m;?c++)?{
????????????????????if?(apple(sum,?row,?col,?n,?c)?>?0)?{
????????????????????????for?(int?s?=?c?+?1;?s?<=?m;?s++)?{
????????????????????????????ways?+=?dp[level?-?1][row][s];
????????????????????????????ways?%=?mod;
????????????????????????}
????????????????????????break;
????????????????????}
????????????????}
????????????????for?(int?r?=?row;?r?<?n;?r++)?{
????????????????????if?(apple(sum,?row,?col,?r,?m)?>?0)?{
????????????????????????for?(int?s?=?r?+?1;?s?<=?n;?s++)?{
????????????????????????????ways?+=?dp[level?-?1][s][col];
????????????????????????????ways?%=?mod;
????????????????????????}
????????????????????????break;
????????????????????}
????????????????}
????????????????dp[level][row][col]?=?ways;
????????????}
????????}
????????result?=?dp[level][1][1];
????}
????for?(int?i?=?0;?i?<=?k;?i++)?{
????????for?(int?j?=?0;?j?<=?n;?j++)?{
????????????free(dp[i][j]);
????????}
????????free(dp[i]);
????}
????free(dp);
????for?(int?i?=?0;?i?<=?n;?i++)?{
????????free(sum[i]);
????}
????free(sum);
????return?result;
}

int?main()?{
????char*?pizza[]?=?{?"A..",?"AAA",?"..."?};
????int?k?=?3;
????int?result1?=?ways1(pizza,?sizeof(pizza)?/?sizeof(pizza[0]),?k);
????int?result2?=?ways2(pizza,?sizeof(pizza)?/?sizeof(pizza[0]),?k);
????printf("Result1:?%d\n",?result1);
????printf("Result2:?%d\n",?result2);
}