[動態規劃]USACO Mar08 遊蕩的奶牛 ctravel 解題報告

【題目描述】
奶牛們在被劃分成N行M列(2 <= N <= 100; 2 <= M <= 100)的草地上遊走，試圖找到整塊草地中最美味的牧草。Farmer John在某個時刻看見貝茜在位置(R1, C1)，恰好T (0 < T <= 15)秒後，FJ又在位置(R2, C2)與貝茜撞了正着。FJ並不知道在這T秒內貝茜是否曾經到過(R2, C2)，他能確定的只是，現在貝茜在那裏。

設S爲奶牛在T秒內從(R1, C1)走到(R2, C2)所能選擇的路徑總數，FJ希望有一個程序來幫他計算這個值。每一秒內，奶牛會水平或垂直地移動1單位距離（奶牛總是在移動，不會在某秒內停在它上一 秒所在的點）。草地上的某些地方有樹，自然，奶牛不能走到樹所在的位置，也不會走出草地。

現在你拿到了一張整塊草地的地形圖，其中'.'表示平坦的草地，'*'表示擋路的樹。你的任務是計算出，一頭在T秒內從(R1, C1)移動到(R2, C2)的奶牛可能經過的路徑有哪些。

程序名: ctravel

輸入格式:

• 第1行: 3個用空格隔開的整數：N，M，T

• 第2..N+1行: 第i+1行爲M個連續的字符，描述了草地第i行各點的情況，保證字符是'.'和'*'中的一個

• 第N+2行: 4個用空格隔開的整數：R1，C1，R2，以及C2

輸入樣例 (ctravel.in):

4 5 6

...*.

...*.

.....

.....

1 3 1 5

輸入說明:

草地被劃分成4行5列，奶牛在6秒內從第1行第3列走到了第1行第5列。

輸出格式:

• 第1行: 輸出S，含義如題中所述

輸出樣例 (ctravel.out):

1

輸出說明:

奶牛在6秒內從(1,3)走到(1,5)的方法只有一種（繞過她面前的樹）。

【分析】

動態規劃。可以用加法原理，這和”過河卒“類似，動態規劃中並不作決策。

狀態設定

F[k][i][j]：前 k秒 走到(i,j)的路徑數。

G[i][j]=1( (i,j)是草地 )，0（(i,j)是樹）

邊界條件：

F[0][R1][C1]=1;

狀態轉移方程：

F[k][i][j]+=Sum{F[k-1][i+1][j]*G[i+1][j],F[k-1][i][j+1]*G[i][j+1],F[k-1][i-1][j]*G[i-1][j],F[k-1][i][j-1]*G[i][j-1]}

目標狀態：

F[T][R2][C2]

【我的代碼】

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
int F[16][101][101];
int G[101][101];
int N,M,T;
int R1,C1;
int R2,C2;

void init()
{
    scanf("%d %d %d\n",&N,&M,&T);
    char c;
    for(int i=1;i<=N;i++)
    {
        for (int j=1;j<=M;j++)
        {
            if(j==M)
                scanf("%c\n",&c);
            else
                scanf("%c",&c);
            if(c=='.')
                G[i][j]=1;
            else
                G[i][j]=0;
        }
    }
    scanf("%d %d %d %d",&R1,&C1,&R2,&C2);
    F[0][R1][C1]=1;
}

void dynamic()
{
    int k=0;
    for (k=1;k<=T;k++)
    {
        for (int i=1;i<=N;i++)
        {
            for (int j=1;j<=M;j++)
            {
                if(!G[i][j])
                    continue;
                F[k][i][j]+=F[k-1][i+1][j]*G[i+1][j];
                F[k][i][j]+=F[k-1][i][j+1]*G[i][j+1];
                F[k][i][j]+=F[k-1][i-1][j]*G[i-1][j];
                F[k][i][j]+=F[k-1][i][j-1]*G[i][j-1];
            }
        }
    }
    printf("%d\n",F[T][R2][C2]);
}

int main()
{
    freopen("ctravel.in","r",stdin);
    freopen("ctravel.out","w",stdout);
    init();
    dynamic();
    return 0;
}

評測結果：

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	10	0.014 s	948 KB	0
2	正确	10	0.002 s	948 KB	0
3	正确	10	0.001 s	948 KB	0
4	正确	10	0.001 s	948 KB	0
5	正确	10	0.007 s	948 KB	0
6	正确	10	0.001 s	948 KB	0
7	正确	10	0.004 s	948 KB	0
8	正确	10	0.001 s	948 KB	0
9	正确	10	0.006 s	948 KB	0
10	正确	10	0.004 s	948 KB	0

运行完成
运行时间 0.040 s
平均内存使用 568 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!