New Game
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
New game是在一个M*M的特殊棋盘（棋盘的第i行都标上了数字i）上进行的新式游戏。给定一个数字N，要求选手把一个棋子从左上角（1，1）移到右下角（M，M），移动时只能往右或往下。要求移动后经过的数字和为N，且拐弯的次数最少。如果对给出的N，选手不能找出移动方案使得经过的数字和为N或找出的路径拐弯次数不是最少，选手就输了。所以，选手一定千方百计要找出满足条件的路径！！
输入
两个正整数M，N（其中M<=16），数据保证有解。输出
最少拐弯数。示例输入
4 22
示例输出
1
爆搜。。基础剪枝即可。
#include#include #include #include #include #include using namespace std; int ma[18][18],m,n,ans; bool vis[18][18]; const int INF=0x3f3f3f3f; int dir[2][2]={{1,0},{0,1}}; void dfs(int x,int y,bool statu,int num,int sum) { //最优剪 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]; int ty=y+dir[i][1]; if(tx>=1&&tx<=m&&ty>=1&&ty<=m&&!vis[tx][ty]) { vis[tx][ty]=1; if(sum==1) dfs(tx,ty,i,num,sum+ma[tx][ty]); else { if(i!=statu) dfs(tx,ty,i,num+1,sum+ma[tx][ty]); else dfs(tx,ty,i,num,sum+ma[tx][ty]); } vis[tx][ty]=0; } } } void init() { for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) ma[i][j]=i; } int main() { while(scanf("%d%d",&m,&n)!=EOF) { memset(vis,0,sizeof(vis)); init(); vis[1][1]=1; ans=INF; dfs(1,1,0,0,1); printf("%d\n",ans); } return 0; }