点击打开链接
题目所属: 隐式图的搜索
题目意思: 给定一个5 x 5 的棋盘,棋盘上面有12个黑色的棋子和12个白色的棋子和一个空格, 最开始的这些棋子的位置是不定的, 要求我们找到最小的步数去把这个棋盘转化为最后的那个样子,最后输出。
解题思路: 我们容易相到的是直接bfs去搜索求出最小步数,但是这一题也可以用dfs+回溯做。首先我们开一个Fin数组用来保存最后的位置,然后就是我们对空格周围的8个方向进行一一的深搜回溯,我们每进行一次搜索就判断是否当前以及到达最后的位置(这个通过judge函数判断),如果是那么判断能否更新ans。其中我们还可以进行优化,就是对于Tans >
10的搜索肯定都是没用的那么我们就可以直接舍去。不用去开vis数组来标记是否走过 , 我们只要限制Tans 小于11即可,如果是Tans 大于10直接return.
代码:
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
using namespace std;
int Fin[5][5] = {//保存最后的结果
{1, 1, 1, 1, 1},
{0, 1, 1, 1, 1},
{0, 0, -1, 1, 1},
{0, 0, 0, 0, 1},
{0, 0, 0, 0, 0},
};
int dir[8][2] = {//方向数组
{-2, -1},
{-2, 1},
{-1, 2},
{1, 2},
{2, 1},
{2, -1},
{1, -2},
{-1, -2}
};
int G[5][5]; //保存输入的位置
char ch;
int t, ans;
struct Point {//坐标结构体
int x;
int y;
};
//判断是否到最后的位置
int judge(){
for(int i = 0 ; i < 5 ; i++){
for(int j = 0 ; j < 5 ; j++){
if(G[i][j] != Fin[i][j])//只要有不像同的就return 0
return 0;
}
}
return 1;
}
//深搜回溯
void dfs(int x , int y , int Tans){//传入三个参数坐标以及步数
if(Tans > 10) return;//大于10步的都不用搜索
if(judge()){//如果这时候满足了,那么判断ans是否大于Tans
if(ans > Tans) ans = Tans;
return;
}
for (int i = 0; i < 8; i++) {//8个方向搜索
if (dir[i][0]+x < 0 || dir[i][0]+x >= 5) continue;//越界就继续下一个方向
if (dir[i][1]+y < 0 || dir[i][1]+y >= 5) continue;//越界就继续下一个方向
swap(G[x][y] , G[dir[i][0]+x][dir[i][1]+y]);//将空格位置交换
dfs(x+dir[i][0] , y+dir[i][1] , Tans+1);//递归继续搜索
swap(G[x][y] , G[dir[i][0]+x][dir[i][1]+y]);//空格从新移回
}
}
//主函数
int main() {
scanf("%d%*c", &t);
while (t--) {
Point p;
//处理输入
for(int i = 0 ; i < 5 ; i++){
for(int j = 0 ; j < 5 ; j++){
if(j == 4) scanf("%c%*c" , &ch);
if(j < 4) scanf("%c" , &ch);
if(ch == ' '){
G[i][j] = -1;
p.x = i ; p.y = j;
}
else G[i][j] = ch-'0';
}
}
ans = 999999999;
dfs(p.x , p.y , 0);
if (ans > 10) printf("Unsolvable in less than 11 move(s).\n");
else printf("Solvable in %d move(s).\n", ans);
}
return 0;
}
分享到:
相关推荐
ai50-projects-2020-x-nights
忠实骑士舰队 忠实骑士舰队(FFK)是一个星际公民组织,旨在成为黑暗宇宙中光的灯塔。 这是在组织的管理领域中使用的当前代码库的monorepo。... 回购中的几乎所有项目都将以/使用功能性范式编写,因此,您将看到遍及...
POLYGON+-+Knights+Pack.unitypackage 美术资源,还不错
INTEL AVX-512 INSTRUCTIONSIN KNIGHTS LANDING PROCESSORSBonan ZhangColfax InternationalMay 11, 2016Abstract This publication is part of a developer guide fo-cusing on the new features in 2nd generation...
POLYGON - Knights Pack 1.2.7z
The Knights Of Alentejo An Android rewrite of a Ludum Dare turn-based adventure game I wrote way back. Guide portuguese knights through a dungeon and kill demons. GooglePlay: ...
这套资源包括中世纪战士、武器、旗帜、建筑等,场景截图可参考博客。喜欢这个风格的朋友,可以查看我的博客,寻找更多优秀资源。
CSCI 3601迭代模板 这是迭代1的入门代码。 此生产模板中包含许多内容,可帮助您入门。 在处理项目时,应使用项目元素替换其中的某些部分,并删除不需要的内容(例如markdown文件,JSON数据文件或实验室的所有残余...
AVX-512 on Intel Knights LandingBerenger BramasMax Planck Computing and Data Facility (MPCDF)Email: Berenger.Bramas@mpcdf.mpg.deThis paper describes fast sorting techniques using the recent AVX-512 ...
python-knights-travail
Intel第二代Xeon Phi产品代号“Knights Landing”(KNL)的架构和技术细节,既可以继续做协处理器,也可以单独做中央主处理器,不再必须有Xeon的支撑,因而更加灵活。采用了14nm新工艺,架构是Silvermont的改进定制版...
POJ2942-Knights of the Round Table 【Tarjan算法】 解题报告+AC代码 http://hi.csdn.net/!s/F3L8HO ================================== 我的POJ所有解题报告:...
蒙·柯尔·奈特斯电影跟踪电影的编码和发行。 资料来源:DVD团队工作人员角色里文·斯卡耶(Riven Skaye) 编码wwwwwwww KFX,定时(歌曲) 拉弗风格定时晚秋TL ak TLC,TL EVA TS
轻骑骑士 在上翻转骑士的方向。 将这个想法 。 该扩展程序可在Chrome网上应用店的。
强大的骑士Capcom的“骑士团之轮”与Capcom的“强大的最后一战”相遇-Sega Master System的争夺战。
两个骑士
Knights ready to protect your kingdom! VR ready. Each model has low polygon count and optimized textures. Great for mobile and hordes! (4 unique body textures and a weapons texture with specular and...
Knights of the round re-edition DEMO v0.1.3 Source Options: Turbo AutoSkipFrame Mute Pause Flash 0.5x 1x 1.5x 2x 3x 4x How to play: <W S A D> Move <J> Attack <K> Jump <P> Pause Try combo keys to ...
leetcode 不会书名:编程骑士 描述 [部署时间:2020 年 5 月 2 日] 这个应用程序是为了展示我在 ...上所做的代码练习,让人们搜索其他 ...katas(代码挑战)时过滤不同的编程语言已经做了。...页面的线框,因为它们是最直接