自动搬运

查看原文

来自洛谷，原作者为

	Imakf **

搬运于2025-08-24 22:06:04，当前版本为作者最后更新于2018-11-05 13:20:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

几万年前出的题目，当时在邀请赛中出的，然后因为宣传邀请赛被禁言了。

这里只讲max的求法，因为min与max求法类似！实在不懂可以私信

$10 pts$ puts("-1");

没什么好说的吧，这个分给的很良心的，虽然这道题巨水

$10 pts$ dfs爆搜

void dfs(int x,int y,bool fac,int step){
  if(x>n||y>m|| 此处有障碍 )	return ;
  //x,y表示当前位置，step表示步数，fac表示方向 (0为向右，1为向下)
  if(x==n&&y==m){
  	ans=max(ans,step);
      return 0;
  }
  if(fac==0){
      dfs(x,y+1,fac,step);
      dfs(x+1,y,fac^1,step+1);
  }
  else{
      dfs(x+1,y,fac,step);
      dfs(x,y+1,fac^1,step)
  }
  
}

不剪枝的搜索必然拿不到高分啦

$50 pts$ dfs加个记忆化

void dfs(int x,int y,bool fac,int step){
  if(x>n||y>m|| 此处有障碍 )	return ;
  if(dis[u][v]>cans)	return;	//jiyihua
  dis[u][v]=max(dis[u][v],cans);	//jiyihua
  if(fac==0){
      dfs(x,y+1,fac,step);
      dfs(x+1,y,fac^1,step+1);
  }
  else{
      dfs(x+1,y,fac,step);
      dfs(x,y+1,fac^1,step)
  }
  
}

$50pts$ bfs

不讲了，写起来很简单

$100pts~~Dp$

这道题是在$2017NOIP$之前出的，当时我是个小蒟蒻鸭（现在还是），不会dp，然后一年之后我再来做了这道题，然后把数据加强了QAQ

$dp[i][j][k]$表示走到$(i,j)$方向为$k$的最多拐弯次数

初始化

把第一行和第一列初始化，第一行肯定不能方向为$1$,第一列方向不能为$0$，如果遇到#那就之后都不能走了

bool a=0;//用来记录是否遇到#
    for(int i=1;i<=n;i++){
        if(_map[i][1]=='#')a=1;
        if(a){
            dis[i][1][1]=10000;
            maxn[i][1][1]=-10000;
        }
        dis[i][1][0]=10000;
        maxn[i][1][0]=-10000;
    }
    a=0;
    for(int j=1;j<=m;j++){
        if(_map[1][j]=='#')a=1;
        if(a){
            dis[1][j][0]=10000;
            maxn[1][j][0]=-10000;
        }
        dis[1][j][1]=10000;
        maxn[1][j][1]=-10000;
    }

转移很简单鸭，跟上面搜索一样的

for(int i=2;i<=n;i++){
       for(int j=2;j<=m;j++){
           if(有障碍)continue;
           maxn[i][j][0]=max(maxn[i][j-1][0],maxn[i][j-1][1]+1);
           maxn[i][j][1]=max(maxn[i-1][j][1],maxn[i-1][j][0]+1);
        }
 }

标程不放了，思路会了就不需要$STD$了