New Game

本是古典何须时尚 2022-12-24 10:56 89阅读 0赞

## New Game ##

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 <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define inf 0x3f3f3f3f
    int map[1100][1100], vis[1100][1100];
    int n, m, direction, sum, step,ans;
    //dx，dy二位坐标标记只能向下或向右（此代码是在第一象限的背景下，只能向上或向右）
    int dx[] = {
        1,0};
    int dy[] = {
        0,1};
    void DFS(int x, int y, int direction, int sum, int step)//x，y是坐标点，direction是方向用0和1代替，sum目前的坐标和，step拐弯次数
    {
        
    	if (sum > n)//坐标和大于给定的要求和，遍历结束
    		return;
    	if (step > ans)//当前拐弯次数小于所有路径的最小拐弯次数，遍历结束
    		return;
    	if (x == m && y == m)//到达指定的坐标位，结束遍历
    	{
        
    		if(sum==n)//目前的坐标和＝要求的坐标和
    		if (ans > step)//取拐弯次数最小的作为ans输出
    			ans = step;
    		return;
    	}
    	for (int i = 0; i < 2; i++)//向上、向右走，方向代替数字1和0
    	{
        
    		int xx = x + dx[i];
    		int yy = y + dy[i];
    		if (vis[xx][yy] == 0 && xx >= 1 && xx <= m && yy >= 1 && yy <= m)//在标记区域内且未遍历
    		{
        
    			vis[xx][yy] = 1;//该点标记为访问
    			if (sum == 1)//sum=1，刚从（1,1）开始出发，向右走或向上走都不是拐弯，所以step即可
    				DFS(xx, yy, i, sum + map[xx][yy], step);
    			else
    			{
        
    				if (i != direction)//与上一步方向不同，拐弯次数+1，即step+1
    					DFS(xx, yy, i, sum + map[xx][yy], step + 1);
    				else//与上一步方向一样，拐弯次数不变，还是step
    					DFS(xx, yy, i, sum + map[xx][yy], step);
    			}
    			vis[xx][yy] = 0;//每次都是两个方向（两个路径），第一次方向下的路径（xx，yy）已遍历，递归后将vis[xx][yy]标为0，因为第二次方向下的路径还未遍历
    		}
    	}
    }
    int main()
    {
        
    	scanf("%d %d", &m, &n);
    	memset(map, 0, sizeof(map));
    	memset(vis, 0, sizeof(vis));
    	for (int i = 1; i <= m; i++)//将坐标图的上坐标点赋值
    	{
        
    		for (int j = 1; j <= m; j++)
    		{
        
    			map[i][j] = i;
    		}
    	}
    	ans = inf;
    	vis[1][1] = 1;//第一个点（1,1）标为访问
    	DFS(1, 1, 0, 1, 0);
    	printf("%d\n", ans);
    }