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;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。