题解 P1535 【游荡的奶牛】

hater · 2019-10-28 12:45:28 · 题解

很有 水 准的题目 那就来篇水的题解

鉴于图论题解就一篇而且解法并不相同 所以介绍新的方法

先建图 把一个坐标为 （ x , y ) 的点在图中成 （x - 1 ) * n + y

数量最小而且不会重复

之后以 ( r2 , c2 ) 作为源点跑最短路

实际的答案也是各个点到 ( r2 , c2 ) 的最短距离 ( 无向图 ）

（ 补充一点 ， 有向图的话要建反图 这里无关不再做解释 ）

之后我们用 dfs 搜索

用一个可行性剪枝

if( dis[(x-1)*n+y] + step > T ) return ; 

就是从这个点走到终点用最短路径也无法在规定时间内达到

那就 return

实际上思路没什么不同就用SPFA装*而已

（然而你也可以用堆优化）

完整代码 想抄的自便

#include <bits/stdc++.h> 
#define MAXN 105
using namespace std ;
char Map[MAXN][MAXN] ;
int n , m , dis[MAXN*MAXN] , T , Ans ,  l[4][2] = {{1,0} , {0,1} , {-1,0} , {0,-1}} ;
int r1 , c1 , r2 , c2 ;
vector <int> v[MAXN*MAXN] ; 
bool In[MAXN*MAXN] ;
queue <int> q ;
void dfs( int x , int y , int step )
{
    if( step > T ) return ;
    if( dis[(x-1)*n+y] + step > T ) return ; 
    if( step == T && x == r2 && y == c2 ) 
    {
        Ans ++ ;
        return ; 
    }
    int tx , ty ;
    for(int i=0; i<4; i++) 
    {
        tx = x+l[i][0] ; ty = y+l[i][1] ;
        if( tx<1 || tx>n || ty<1 || ty>m ) continue ;
        if( Map[tx][ty] == '*' ) continue ;
        dfs( tx , ty , step+1 ) ;
    }
}
int main() 
{
    int S , E ;
    cin >> n >> m >> T ;
    for(int i=1; i<=n; i++)
      for(int j=1; j<=m; j++)
        cin >> Map[i][j] ;
    cin >> r1 >> c1 >> r2 >> c2 ;
    S = (r1-1)*n+c1 ; E = (r2-1)*n+c2 ;
    for(int i=1; i<=n; i++)
      for(int j=1; j<=m; j++)
       for(int k=0; k<4; k++)
       {
         int tx = i+l[k][0] , ty = j+l[k][1] ;
         if( tx<1 || tx>n || ty<1 || ty>m ) continue ;
         if( Map[tx][ty] == '*' ) continue ;
         int x = (i-1)*n+j , u = (tx-1)*n+ty  ;
         v[x].push_back( u ) ;
       }
    memset( dis , 0x3f , sizeof(dis) ) ;
    dis[E] = 0 ; In[E] = 1 ; q.push(E) ;
    while(!q.empty()) 
    {
        int x = q.front(); q.pop() ; In[x] = 0 ;
        for(int i=0; i<v[x].size(); i++)
        {
            int u = v[x][i] ;
            if( dis[u] > dis[x]+1 )
            {
                dis[u] = dis[x]+1 ;
                if( !In[u] ) 
                {
                    In[u] = 1;
                    q.push(u) ;
                }
            }
        }
    }
    dfs( r1 , c1 , 0 ) ; 
    return 0 ;
}