SDUT 1125 New Game 【 DFS 】
New SDUT DFS Game
2023-06-13 09:15:39 时间
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
题解: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;
}
相关文章
- 用new创建数组
- 小技巧:通过 New-Ailas 指令在 Powershell 上启动多个不同版本的应用程序
- java中的new BufferedReader(new InputStreamReader(System.in))「建议收藏」
- C/CPP中的malloc和new的差异
- 【错误记录】Groovy 注入方法报错 ( Cannot add new method [hello] for arguments [[]]. It already exists )
- ORA-32403: cannot use new values from mv log on “string”.”string” ORACLE 报错 故障修复 远程处理
- ORA-44802: No new plan (classifier list) has been submitted ORACLE 报错 故障修复 远程处理
- MySQL Error number: MY-010822; Symbol: ER_BINLOG_CANT_GENERATE_NEW_FILE_NAME; SQLSTATE: HY000 报错 故障修复 远程处理
- ORA-04076: invalid NEW or OLD specification ORACLE 报错 故障修复 远程处理
- ORA-14046: a partition may be split into exactly two new partitions ORACLE 报错 故障修复 远程处理
- C++基础入门教程(五):new和delete