题目描述
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;
}
解析
暂无
