若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1958: New Game

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,349

题目描述

New game是在一个M*M的特殊棋盘(棋盘的第i行都标上了数字i)上进行的新式游戏。给定一个数字N,要求选手把一个棋子从左上角(1,1)移到右下角(M,M),移动时只能往右或往下。要求移动后经过的数字和为N,且拐弯的次数最少。
如果对给出的N,选手不能找出移动方案使得经过的数字和为N或找出的路径拐弯次数不是最少,选手就输了。所以,选手一定千方百计要找出满足条件的路径!!

输入

两个正整数M,N(其中M<=16),数据保证有解。

输出

最少拐弯数。

样例输入

4 22

样例输出

1

参考代码

#include<stdio.h>
#include<string.h>
int ma[100][100],n,tol;
int vis[100][100];
int INF=0x3f3f3f3f;
int ans;
int dir[2][2]={0,1,1,0};
void dfs(int x,int y,int stat,int gw,int sum) 
{
    if(gw>ans)return ;
    if(sum>tol)return ;
    if(x==n&&y==n) 
    {
        if(sum==tol)
                    ans=ans<gw?ans:gw;
        return ;
    }
    for (int i=0;i<2;i++) 
    {
        int xx=x+dir[i][0];
        int yy=y+dir[i][1];
        if(xx>0&&xx<n+1&&yy>0&&yy<n+1&&!vis[xx][yy]) 
        {
            vis[xx][yy]=1;
            if(sum==1)
                            dfs(xx,yy,i,gw,sum+ma[xx][yy]); else 
            {
                if(i!=stat)
                                    dfs(xx,yy,i,gw+1,sum+ma[xx][yy]); else dfs(xx,yy,i,gw,sum+ma[xx][yy]);
            }
            vis[xx][yy]=0;
        }
    }
}
int main() 
{
    scanf("%d%d",&n,&tol);
    int i,j;
    for (i=1;i<=n;i++)
            for (j=1;j<=n;j++)
            ma[i][j]=i;
    ans=INF;
    vis[1][1]=1;
    dfs(1,1,0,0,1);
    printf("%dn",ans);
    return 0;
}

解析

暂无

hustoj

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

原站点 Skip Dreams孤独患者
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist