障碍路线Obstacle Course

P1649 [USACO07OCT]障碍路线Obstacle Course

裸的dfs，今天学了一个新招，就是在过程中进行最优性减枝。

#include<bits/stdc++.h>

using namespace std;

int n,sx,sy,ex,ey,ans=;

char a[][];

int d[][];

int x[]={-,,,};

int y[]={,,,-};

bool vis[][];

void dfs(int nx,int ny,int dir,int num)

{

    if(nx>n||nx<||ny>n||ny<||vis[nx][ny]||ans==)

    return;

    if(a[nx][ny]=='x')

    return;

    if(num>=ans)

    return ;

    if(num>d[nx][ny])

    return;

    d[nx][ny]=num;

    if(nx==ex&&ny==ey)

    {

        if(num<ans)

        ans=num;

        return ;

    }

    for(int i=;i<;i++)

    {

        if((abs(i-dir)==||abs(i-dir)==)&&nx+x[i]>&&ny+y[i]>&&!vis[nx+x[i]][ny+y[i]])

        {

        vis[nx][ny]=true;

        dfs(nx+x[i],ny+y[i],i,num);

        vis[nx][ny]=false;

        }

        else

        if(!vis[nx+x[i]][ny+y[i]]&&nx+x[i]>&&ny+y[i]>)

        {

        vis[nx][ny]=true;

        dfs(nx+x[i],ny+y[i],i,num+);

        vis[nx][ny]=false;

        }

    }

}

int main()

{

  cin>>n;

  for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)

      {

          cin>>a[i][j];

          if(a[i][j]=='A')

          sx=i,sy=j;

          if(a[i][j]=='B')

          ex=i,ey=j;

      }

    for(int i=;i<=n;i++)

    for(int j=;j<=n;j++)

      {

          d[i][j]=;

      }

  for(int i=;i<;i++)

      dfs(sx+x[i],sy+y[i],i,);

  if(ans!=)

  cout<<ans;

  else

  cout<<-;

  return ;

}