SDUT 1125 New Game 【 DFS 】

Lokinli

发布于 2023-03-09 06:30:09

12700

代码可运行

文章被收录于专栏：以终为始以终为始

运行总次数：0

代码可运行

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

题解：DFS 搜索，注意判断拐弯的次数，第一次无论是向右还是向下都是不算的，只有路径发生变化，才算是，所以可以设置一个 flag 值，因为只有向下和向右两种情况，只要是0 和 1 就可以，与上次不相同， num ++ 。最后还是看了一下题解才知道自己错哪里了。

（愈来愈菜，嘤）

#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("%d\n",ans);
    return 0;
}