题解 P1535 【游荡的奶牛】

Drinkwater · 2017-08-02 21:54:27 · 题解

其实就是搜索加上剪枝，限制一个搜索层数，限制一个搜索步数就好了（楼下题解没代码，蒟蒻瑟瑟发抖>_>）

/*****

 > Author: Drinkwater
 > Created Time: 2017/8/2 20:48:05

****/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>

prag\

ma GCC optimize("O3")
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
#define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i)
#define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i)
#define mem(a, b) memset((a), b, sizeof(a))
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
int read()
{
    register int sum = 0,fg = 0;char c = getchar();
    while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }
    while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }
    return fg ? -sum : sum;
}
const int inf = 1e9;
const int maxn = 100000;
int vis[110][110],n,m,t,xs,ys,xt,yt;
char s[110];
int mo[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int ans = 0;
void dfs(int x,int y,int st)
{
    if (x == xt && y == yt && st == t) { ans++; return; }
    if (st == t) return;
    REP(i,0,3)
    {
        int xx = x + mo[i][0];
        int yy = y + mo[i][1];
        if (xx < 1 || xx > n || yy < 1 || yy > m || vis[xx][yy]) continue;
        if (st + 1 + abs(xt - xx) + abs(yt - yy) > t) continue;
        if (st + 1 <= t) dfs(xx,yy,st+1);
    }
}
int main()
{
    n = read(), m = read(), t = read();
    REP(i,1,n)
    {
        gets(s);
        REP(j,0,m-1)vis[i][j+1] = (s[j] == '*');
    }
    xs = read(), ys = read(),xt = read(), yt = read();
    dfs(xs,ys,0);
    cout<<ans<<endl;
    return 0;
}