题目描述

在一个M×N的板上，有部分格子被标记为障碍（例如上图黑色标示的格子）。你任选一个空白格子放置一个小球（如上图灰点所示），并选择小球滚动的方向（上，下，左，右），小球将在板上一直滚动直至它碰到障碍，或板的边界，或它之前经过的格子。如果小球遇到以上情况之一将停下，你可以给它另选滚动的方向，然后小球将以同样的方式前进。如果小球在四个方向上都无法继续滚动，游戏结束，这时假如小球的轨迹覆盖板上所有的空白格子，你将获胜。上图展示的轨迹就是一个仅用10步获胜的例子。
你的任务是对给定板子，计算赢得游戏所需的最少步数。

思路

暴力dfs求解
从每一个点开始搜，记录一个可以走的总点数lf，每次走就lf–
若lf=1输出0

#include <stdio.h>
#include <string>
#include <queue>
#include <iostream>
#include <cstring>
using namespace std;
#define maxn 31
#define fill(x,y) memset(x,y,sizeof(x))
#define INF 0x7f7f7f7f
#define max(x,y) x>y?x:y
int ans=INF,n,m,lf,ls,xx,yy;
int a[maxn][maxn],f[maxn][maxn];
int dx[5]={0,1,0,-1,0};
int dy[5]={0,0,1,0,-1};
int dfs(int x,int y,int st)
{
    for (int i=1;i<=4;i++)
    {
        int lx=x,ly=y,l=0;
        while (lx+dx[i]<=m&&lx+dx[i]>=1&&ly+dy[i]<=n&&ly+dy[i]>=1&&!a[lx+dx[i]][ly+dy[i]]&&!f[lx+dx[i]][ly+dy[i]]&&(lx+dx[i]!=xx||ly+dy[i]!=yy))
        {
            f[lx+dx[i]][ly+dy[i]]=st+1; ls--;
            lx+=dx[i];ly+=dy[i];
        }
        if (lx!=x||ly!=y)
        {
            if (ls==1&&st+1<ans) ans=st+1;
            dfs(lx,ly,st+1);
        }
        for (int j=1;j<=4;j++)
        {
            int lx=x,ly=y,l=0;

            while (lx+dx[j]<=m&&lx+dx[j]>=1&&ly+dy[j]<=n&&ly+dy[j]>=1&&!a[lx+dx[j]][ly+dy[j]]&&f[lx+dx[j]][ly+dy[j]]==st+1&&(lx+dx[j]!=xx||ly+dy[j]!=yy))
            {
                ls++;
                f[lx+dx[j]][ly+dy[j]]=0;
                lx+=dx[j];ly+=dy[j];
            }
        }
    }

}
int main()
{
    scanf("%d%d",&n,&m);
    lf=n*m;
    for (int i=1;i<=n;i++)
    {
        char ch[maxn];
        cin>>ch;
        for (int j=0;j<m;j++)
            if (ch[j]=='*') 
            {
                a[i][j+1]=1;
                lf--;
            }
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (!a[i][j]) 
            {
                ls=lf;
                fill(f,0);
                xx=i,yy=j;
                f[i][j]=0;
                dfs(i,j,0);
            }
    if (ans==INF) ans=-1;
if (lf==1) ans=0;
    printf("%d\n",ans);
}