Bzoj 1085: [SCOI2005]骑士精神 (dfs)
2024-09-08 06:17:12
Bzoj 1085: [SCOI2005]骑士精神
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1085
dfs + 剪枝.
剪枝方法:
1.每次交换只能改变一个位置.若发现之间相差的步数加上以前走的步数大于15的话,直接舍弃这一状态.
2.初始时,\(ans\)设为\(16\)
有了上面两个剪枝就A了.
照这节奏,SCOI2005就刷完了???
#include <iostream>
#include <cstdio>
#define X 6
using namespace std;
const int gx[] = {0,-2,-2,-1,-1,1,1,2,2};
const int gy[] = {0,-1,1,-2,2,-2,2,-1,1};
char map[X][X];
char c[X][X] = {
'0','0','0','0','0','0',
'0','1','1','1','1','1',
'0','0','1','1','1','1',
'0','0','0','*','1','1',
'0','0','0','0','0','1',
'0','0','0','0','0','0'
};
int ans;
int inint(){
int num = 0;
for(int i = 1;i <= 5;++ i){
for(int j = 1;j <= 5;++ j){
if(c[i][j] != map[i][j])num ++;
}
}
return num;
}
void dfs(int x,int y,int d,int tmp){
int l = inint();
if(d + l > 16)return;
if(d > ans)return;
if(l == 0) ans = d;
for(int i = 1;i <= 8;++ i){
if(x + gx[i] < 1 || x + gx[i] > 5)continue;
if(y + gy[i] < 1 || y + gy[i] > 5)continue;
if(tmp + i == 9)continue;
swap(map[x][y],map[x + gx[i]][y + gy[i]]);
dfs(x + gx[i],y + gy[i],d + 1,i);
swap(map[x][y],map[x + gx[i]][y + gy[i]]);
}
}
void work(){
int x,y;
for(int i = 1;i <= 5;++ i)cin >> map[i] + 1;
for(int i = 1;i <= 5;++ i){
for(int j = 1;j <= 5;++ j){
if(map[i][j] == '*')
x = i,y = j;
}
}
ans = 16;
dfs(x,y,0,0);
printf("%d\n",ans == 16 ? -1 : ans);
return;
}
int main(){
int t;
scanf("%d",&t);
while(t --){
work();
}
return 0;
}
最新文章
- POJ3928Ping pong[树状数组 仿逆序对]
- 高性能MySQL笔记:第1章 MySQL架构
- js 完成对图片的等比例缩放的方法
- USB DATA Toggle
- 用vmware安装gho文件
- Java多线程中易混淆的概念
- 二、Cocos2dx概念介绍(游戏开发中不同的坐标系,cocos2dx锚点)
- php数组的使用
- 读Zepto源码之集合操作
- python 三级菜单 while循环三次,湖北省市-县-街道的选择,3个while的循环 -day2
- SpringBoot运行原理
- mysql 的crud操作(增删改查)
- 版本控制commit和update过程
- windows下《Go Web编程》之Go开发工具
- node库的选择
- mfc CFileDialog类
- BZOJ5020 [THUWC 2017]在美妙的数学王国中畅游LCT
- 转载nginx+uwsgi+django
- Java并发编程:线程池
- QT STUDY