N - New Game（DFS+剪枝）

Description
New game是在一个M*M的特殊棋盘（棋盘的第i行都标上了数字i）上进行的新式游戏。给定一个数字N，要求选手把一个棋子从左上角（1，1）移到右下角（M，M），移动时只能往右或往下。要求移动后经过的数字和为N，且拐弯的次数最少。
如果对给出的N，选手不能找出移动方案使得经过的数字和为N或找出的路径拐弯次数不是最少，选手就输了。所以，选手一定千方百计要找出满足条件的路径！！
Input
两个正整数M，N（其中M<=16），数据保证有解。
Output
最少拐弯数。
Sample
Input
4 22
Output
1

#include<bits/stdc++.h>#define INF 0x3f3f3f3f using namespace std;const int N = 35;int m, n; int book[N][N]; int mp[N][N]; int dir[2][2] = {{1, 0}, {0, 1}}; int minn;void DFS(int x, int y, int flag, int id, int cnt) {if(id > minn) //最优剪return ;if(cnt > n) //可行剪return ;if(x == m && y == m){if(cnt == n){minn = min(minn, id);}return ;}for(int i = 0; i < 2; i++){int xx = x + dir[i][0];int yy = y + dir[i][1];if(xx >= 1 && xx <= m && yy >= 1 && yy <= m && !book[xx][yy]){book[xx][yy]=1;if(cnt == 1){DFS(xx, yy, i, id, cnt + mp[xx][yy]);}else{if(i != flag)DFS(xx, yy, i, id + 1, cnt + mp[xx][yy]);elseDFS(xx, yy, i, id, cnt + mp[xx][yy]);}book[xx][yy] = 0;}} }void init() {for(int i = 1; i <= m; i++){for(int j = 1; j <= m; j++)mp[i][j] = i;} } int main() {while(cin >> m >> n){memset(book, 0, sizeof(book));init();book[1][1] = 1;minn = INF;DFS(1, 1, 0, 0, 1);cout << minn << endl;}return 0; }

总结

以上是生活随笔为你收集整理的N - New Game（DFS+剪枝）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。