P1560 [USACO5.2]蜗牛的旅行Snail Trails 题解

Exber · 2021-04-22 17:34:29 · 题解

题意

• 给你一个 n*n 的棋盘，棋盘上有一些障碍。

• 一直很笨的蜗牛会沿着某个方向一直走，撞到墙它可以左拐或者右拐，遇到自己已经走过的格子它就停下来不走了。

• 现在这只蜗牛从 (1,1) 的位置出发，请问它最多能走多少格。

做法

这道题其实相当于一个 dfs 的模板。

可是，为什么 dfs 不会超时？

障碍数可是达到了 200 的，时间复杂度不是会达到 O(2^{200}) 吗？

原因很简单，因为每一个格子只能走一遍，所以时间复杂度并没有那么高，只有 O(n^2)。

AC 代码

#include <iostream>
#include <cstdio>

using namespace std;

int n,m,mp[125][125],dx[]{0,0,1,-1},dy[]{1,-1,0,0};
bool vis[125][125];

inline bool can(int x,int y)
{
    return x>=1&&x<=n&&y>=1&&y<=n&&mp[x][y]==0&&!vis[x][y];
}

int count(int x,int y,int f)
{
    int nx=x+dx[f],ny=y+dy[f]; // 下一步的位置 
    if(vis[nx][ny]) // 走过了，不用走了 
    {
        return 1;
    }
    int ans=0;
    if(!can(nx,ny)) // 撞墙了 
    {
        for(int i=0;i<4;i++) // 枚举转弯方向 
        {
            int nnx=x+dx[i],nny=y+dy[i]; // 转弯后的位置 
            if(can(nnx,nny)) // 能走就一定是往左或者往右 
            {
                vis[nnx][nny]=true; // 标记 
                ans=max(ans,count(nnx,nny,i)); // 往新方向走 
                vis[nnx][nny]=false; // 取消标记 
            }
        }
    }
    else
    {
        vis[nx][ny]=true; // 标记 
        ans=count(nx,ny,f); // 一直往这个方向走下去 
        vis[nx][ny]=false; // 取消标记 
    }
    return ans+1; // 记得加上当前格 
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        char x;
        int y;
        scanf(" %c%d",&x,&y); // 注意一下输入格式
        mp[x-'A'+1][y]=1;
    }
    vis[1][1]=true; // 起点走过了 
    printf("%d\n",max(count(1,1,0),count(1,1,2))); // 往左和往下 
    return 0;
}