New Game

New Game

时间: 1ms        内存:64M

描述:

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

输入:

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

输出:

最少拐弯数。

示例输入:

4 22

示例输出:

1

提示:

参考答案(内存最优[1168]):

#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("%d\n",ans);
    return 0;
}

参考答案(时间最优[0]):

//整体思路为爆搜剪枝

#include <iostream> 
#include <stdio.h> 
#include <math.h> 
#include <string.h> 
#include <stdlib.h> 
using namespace std; 
  
const int INF=0x3f3f3f3f; //设为无穷大
int n,m,ans; 
int map[18][18]; 
bool visited[18][18]; //是否访问过
int dir[2][2]={ {1,0},{0,1} }; //方向,右和下
  
void init() //初始化地图,给每个格赋值
{ 
    for(int i=1;i<=m;i++) 
        for(int j=1;j<=m;j++) 
           map[i][j]=i; 
} 

int min(int a,int b)//求最小值
{
	if(a<b)
		return a;
	return b;
}
  
void dfs(int x,int y,int now_dir,int num,int sum) 
{ //深搜,变量依次为:当前位置的坐标x,y,当前的方向,转弯的数量,经过的数字的和
    if(num>ans) return ; //剪枝
    if(sum>n) return ; //剪枝
    if(x==m&&y==m) //若到达目的地
    { 
        if(sum==n) 
            ans=min(ans,num); 
        return ; 
    } 
    for(int i=0;i<2;i++) //向下或向右进行搜索
    { 
        int tx=x+dir[i][0]; //走一步后位置的做标tx,ty
        int ty=y+dir[i][1]; 
        if(tx>=1&&tx<=m&&ty>=1&&ty<=m&&!visited[tx][ty]) 
        { //若这一步能走,则把标记改为走过,(visited[tx][ty]=1; )
            visited[tx][ty]=1; 
            if(sum==1) //若为走的第一步,则直接去下一步递归搜索
				dfs(tx,ty,i,num,sum+map[tx][ty]); 
            else
            { 
                if(i!=now_dir) //若当前方向与下一步要走的方向不一致,则转弯数加一,去下一步递归搜索
                    dfs(tx,ty,i,num+1,sum+map[tx][ty]); 
                else	//若一直,则转弯数不变,去下一步递归搜索
                    dfs(tx,ty,i,num,sum+map[tx][ty]); 
            } 
            visited[tx][ty]=0; //走完后将此位置标记改为没走过
        } 
    } 
} 
  
int main() 
{ 
    memset(visited,0,sizeof(visited)); //将visited数组全部置为0,具体用法请百度
    visited[1][1]=1; //将其实位置置为走过
    cin>>m>>n; 
    init(); //初始化地图
    ans=INF; 
    dfs(1,1,0,0,1); 
    cout<<ans<<endl; 
    return 0; 
} 

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

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