SSL 2635_最小转弯问题_dfs

发布于 2019-05-19  5 次阅读


题目描述

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


思路

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


#include 
#include 
#include 
#include 
#include 
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=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
]]>