Description
New game是在一个M*M的特殊棋盘（棋盘的第i行都标上了数字i）上进行的新式游戏。给定一个数字N，要求选手把一个棋子从左上角（1，1）移到右下角（M，M），移动时只能往右或往下。要求移动后经过的数字和为N，且拐弯的次数最少。 如果对给出的N，选手不能找出移动方案使得经过的数字和为N或找出的路径拐弯次数不是最少，选手就输了。所以，选手一定千方百计要找出满足条件的路径！！
Input
两个正整数M，N（其中M<=16），数据保证有解。
Output
最少拐弯数。
Sample
Input
代码语言：javascript复制4 22Output
代码语言：javascript复制1题解：DFS 搜索，注意判断拐弯的次数，第一次无论是向右还是向下都是不算的，只有路径发生变化，才算是，所以可以设置一个 flag 值，因为只有向下和向右两种情况，只要是0 和 1 就可以，与上次不相同， num 。最后还是看了一下题解才知道自己错哪里了。
（愈来愈菜，嘤）
代码语言：javascript复制#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <bits/stdc .h>
using namespace std;
const int N = 500;
const int inf = 0x3f3f3f3f;
int n,m,ans;
int gra[N][N];
int vis[N][N];
int dx[4] = {1,0};
int dy[4] = {0,1};
// sum 是到目前为止的和
// num 是转弯的次数
void dfs(int x, int y,int flag, int sum, int num)
{
if(sum > n) return ;
if(num > ans) return ;
if(x == m && y == m){
if(sum == n){
ans = min(ans,num);
}
return ;
}
for(int i = 0; i <= 1; i ) {
int tx = x dx[i];
int ty = y dy[i];
if(tx >= 1 && tx <= m && ty >= 1 && ty <= m && !vis[tx][ty]){
vis[tx][ty] = 1;
if(sum==1)
dfs(tx,ty,i,sum gra[tx][ty],num);
else
{
if(i!=flag)
dfs(tx,ty,i,sum gra[tx][ty],num 1);
else
dfs(tx,ty,i,sum gra[tx][ty],num);
}
vis[tx][ty]=0;
}
}
}
int main()
{
scanf("%d %d", &m, &n);
memset(vis,0,sizeof(vis));
for(int i = 1; i <= m; i ){
for(int j = 1;j <= m; j ){
gra[i][j] = i;
}
}
ans = inf;
vis[1][1] = 1;
dfs(1,1,0,1,0);
printf("%dn",ans);
return 0;
}
