[BZOJ] 1616: [Usaco2008 Mar]Cow Travelling游荡的奶牛

1616: [Usaco2008 Mar]Cow Travelling游荡的奶牛

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 1312  Solved: 736
[Submit][Status][Discuss]

Description

奶牛们在被划分成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)的奶牛可能经过的路径有哪些。

Input

* 第1行: 3个用空格隔开的整数：N，M，T

* 第2..N+1行: 第i+1行为M个连续的字符，描述了草地第i行各点的情况，保证 字符是'.'和'*'中的一个 * 第N+2行: 4个用空格隔开的整数：R1，C1，R2，以及C2

Output

* 第1行: 输出S，含义如题中所述

Sample Input

4 5 6
...*.
...*.
.....
.....
1 3 1 5

输入说明:

草地被划分成4行5列，奶牛在6秒内从第1行第3列走到了第1行第5列。

Sample Output

1

奶牛在6秒内从(1,3)走到(1,5)的方法只有一种（绕过她面前的树）。

HINT

 

Source

Silver

Analysis

蒟蒻只看出这是暴搜 qwq

首先一个限定 T 步的DFS（这样可以防止路径重复）

证明：显然（不会证啊qwq）

定义计数图 cnt [ x ] [ y ] ，保存可到达点 ( x , y ) 的路径总数

然后某一次路径搜索在哪里终结，就在对应点的计数图上 +1

好的，6000+ms 为某位大佬的权限号贡献一个TLE

考虑剪枝

如果一条路径无法到达目的地，那么这条路径显然是可以剪枝剪掉的

定义最短距离图 Tracing [ x ] [ y ] ，保存目的地到点 ( x , y ) 的最短距离

如果在DFS的某个状态中，剩余的步数已经不够到达了，敢敢剪掉

上述算法用时 3288ms

---

然后我研究了一下其他人的版本

发现是一个什么都不是的DP

QwQ

定义 DP [ t ] [ x ] [ y ] 为第 t 秒可以到达点 ( x , y ) 的总路径数

那么我们可以暴力了

代码已Po

其实早先也有想到类似解法，但是如何防止新求出来的答案互相覆盖呢？（天真的我一直局限于用一张地图= =）

根据时间区别，不停绘制新地图，就类似上述的DP状态定义

还是太年轻啊，唉

DP用时：44ms

Code

#include<cstdio>
#include<iostream>
using namespace std;

const int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};

int r,c,t,sx,sy,tx,ty;
int map[1000][1000];
int DP[20][1000][1000];
char str[1000];

int main(){
    scanf("%d%d%d",&r,&c,&t);
    for(int i = 1;i <= r;i++){
        scanf("%s",str);
        for(int j = 1;j <= c;j++){
            if(str[j-1] == '.') map[i][j] = 1;
        }
    }scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
    
    DP[0][sx][sy] = 1;
    
    for(int T = 1;T <= t;T++){
        for(int i = 1;i <= r;i++){
            for(int j = 1;j <= c;j++){
                for(int k = 0;k < 4;k++){
                    int nowx = i+dir[k][0];
                    int nowy = j+dir[k][1];
                    if(!map[nowx][nowy]) continue;
                    DP[T][i][j] += DP[T-1][nowx][nowy];
                }
            }
        }
    }
    
    printf("%d",DP[t][tx][ty]);
    
    return 0;
}

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;

struct node{
    int x,y,step;
};

const int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int r,c,t,sx,sy,tx,ty;
int map[1000][1000];
int tracing[1000][1000];
int cnt[1000][1000];
bool book[1000][1000];
char ctr;

void bfs(){
    queue<node> Q;
    Q.push((node){tx,ty,0});
    tracing[tx][ty] = -1;
    
    while(!Q.empty()){
        node now = Q.front();
        Q.pop();
        
        for(int i = 0;i < 4;i++){
            int nowx = now.x+dir[i][0];
            int nowy = now.y+dir[i][1];
            if((!tracing[nowx][nowy] || tracing[nowx][nowy] >= now.step+1) && map[nowx][nowy]){
                tracing[nowx][nowy] = now.step+1;
                if(!book[nowx][nowy]){
                    Q.push((node){nowx,nowy,now.step+1});
                    book[nowx][nowy] = true;
                }
            }
        }
        book[now.x][now.y] = false;
    }
}

void dfs(int nowx,int nowy,int step){
    if(step == t) cnt[nowx][nowy]++;
    else{
        for(int i = 0;i < 4;i++){
            int x = nowx+dir[i][0];
            int y = nowy+dir[i][1];
            
            if(map[x][y] && step+tracing[x][y] <= t) dfs(x,y,step+1);
        }
    }
}

int main(){
    scanf("%d%d%d",&r,&c,&t);
    for(int i = 1;i <= r;i++){
        for(int j = 1;j <= c;j++){
            cin >> ctr;
            if(ctr == '.') map[i][j] = 1;
        }
    }
    
    scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
    
    bfs();
    
    dfs(sx,sy,0);
    
    printf("%d",cnt[tx][ty]);
    
//    for(int i = 1;i <= r;i++){
//    /cout << endl;
//        for(int j = 1;j <= c;j++){
//            printf("%d ",tracing[i][j]);
//        }
//    }
    
    return 0;
}