题解 P1713 【麦当劳叔叔的难题】

谢谢_对不起 · 2019-10-09 08:41:55 · 个人记录

经典迷宫问题+记忆化DFS

和经典迷宫问题一样，但此题暴搜会TLE一个点，所以要加一个记忆化。
本人代码比较适合初学者观看，个人认为比较好懂

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,m;
int a[101][101];
int f[101][101],ma[101][101],mi[101][101];
int maxx=0,minn=0x3f3f3f3f;
void dfs(int q,int p,int ans)
{
    if(q<1||q>n||p<1||p>n||a[q][p]==1)return;
    if(ans>=minn&&ans<=ma[q][p])return;
    f[q][p]=ans;    
    if(q==1&&p==n)
    {
        if(ans<minn)
          {
            for(int i=1;i<=n;i++)
              for(int j=1;j<=n;j++)
            {
             mi[i][j]=f[i][j];  
            }
            minn=ans;
          }
        if(ans>maxx)
        {
            for(int i=1;i<=n;i++)
              for(int j=1;j<=n;j++)
            {
             ma[i][j]=f[i][j];  
            }
            maxx=ans;
        }
        return;
    }

    a[q][p]=1;
    dfs(q+1,p,ans+1);
    dfs(q,p+1,ans+1);
    dfs(q,p-1,ans+1);
    dfs(q-1,p,ans+1);
    a[q][p]=0;
    f[q][p]=0;
    return;
}
int main()
{
   scanf("%d%d",&n,&m);
   int x,y;
   for(int i=1;i<=m;i++)
      {
      scanf("%d%d",&x,&y);
      a[x][y]=1;
      }
       for (int i=1;i<=n;i++)
        for (int j=1;j <=n;j++)
        ma[i][j]=-1,mi[i][j]=0x7ffffff;
   dfs(n,1,1);
   cout<<maxx-minn;
   return 0;
}