kuangbin专题——简单搜索

A - 棋盘问题

题意

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

解法：n皇后的变形，注意放的位置不一定，并不是每一行都要放，计个step，然后dfs每一个点时，记得回溯上去处理一下，把vis[i]置为0，step--即可，然后处理完此次结束后，dfs（x+1),处理下一位；

#include<cstdio>

#include<cstring>

using namespace std;

#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)

#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)

int step,ans,n,k;

char mp[][];

bool vis[];

void dfs(int x){

     if(step==k){

     ans++;

     return ;

     }

     if(x>=n)return ;

     for(int i=;i<n;i++){

     if(!vis[i]&&mp[x][i]=='#'){

     step++;

     vis[i]=;

     dfs(x+);

     vis[i]=;

     step--;

     }

     }

     dfs(x+);

}

int main(){

    while(~scanf("%d %d",&n,&k)){

    memset(vis,,sizeof vis);

    if(n+k<)break;

    rep(i,,n-){

    scanf("%s",mp[i]);

    }

    ans=step=;

    dfs();

    printf("%d\n",ans);

    }

    return ;

}

B - Dungeon Master

POJ - 2251

题意:就是个三维迷宫，直接广搜即可，用一个方向数组

#include<bits/stdc++.h>

#include<queue>

#include<cstring>

using namespace std;

#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)

#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)

#define pb push_back

#define fi first

#define se second

typedef long long ll;

typedef unsigned long long ull;

typedef long double ldb;

const int maxn=1e5+;

bool isprime[maxn];

void makeprime(){

     memset(isprime,true,sizeof isprime);

     isprime[]=;

     for(int i=;i*i<=maxn;i++){

     if(isprime[i]==)continue;

     for(int j=i*;j<=maxn;j+=i){

     isprime[j]=;

     }

     }

//     rep(i,1,maxn){

//     cout<<i<<" "<<isprime[i]<<endl;

//     }

}

struct point{int num,step;};

int ans,p,q;

bool vis[maxn];

bool  bfs(){

      memset(vis,,sizeof vis);

     vis[p]=;

     point tmp,next;

     tmp.num=p,tmp.step=;

     queue<point>Q;

     Q.push(tmp);

     while(!Q.empty()){

     tmp=Q.front();

     Q.pop();

     vis[tmp.num]=;

     if(tmp.num==q){

     ans=tmp.step;

     return true;

     }

     int t=tmp.num;

     for(int i=;i<;i++){

     for(int j=;j<=;j++){

     t=tmp.num;

     if(i==){

     t-=t%;

     t+=j;

     }

     else if(i==){

     t-=t%/*;

     t+=j*;

     }

     else if(i==){

     t-=t%/*;

     t+=j*;

     }

     else if(i==){

     t-=t%/*;

     t+=j*;

     }

     if(t==tmp.num||t<||vis[t]||!isprime[t])continue;

     next.num=t,next.step=tmp.step+;

     vis[t]=;

     Q.push(next);

     }

     }

     }

     return false;

}

int main(){

    makeprime();

    int cas;

    scanf("%d",&cas);

    while(cas--){

    memset(vis,,sizeof vis);

    scanf("%d %d",&p,&q);

    ans=;

    if(bfs())printf("%d\n",ans);

    else printf("Impossible\n"); 

    }

    return ;

}

C - Catch That Cow

POJ - 3278

题意：给你n和m，问几步能走到，直接广搜即可

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)

#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)

#define pb push_back

#define fi first

#define se second

#define check(x) (x<=N&&x>=0)

typedef long long ll;

typedef unsigned long long ull;

typedef long double ldb;

const int N=1e5+;

bool vis[N];

int step[N];

int n,k;

void bfs(){

     queue<int>Q;

     vis[n]=;

     step[n]=;

     Q.push(n);

     while(!Q.empty()){

     int s=Q.front();

     if(s==k)return ;

     Q.pop();

     if(check(s+)&&!vis[s+]){

     vis[s+]=;

     step[s+]=step[s]+;

     Q.push(s+);

     }

     if(check(s-)&&!vis[s-]){

     vis[s-]=;

     step[s-]=step[s]+;

     Q.push(s-);

     }

     if(check(s<<)&&!vis[s<<]){

     vis[s<<]=;

     step[s<<]=step[s]+;

     Q.push(s<<);

     }

     }

}

int main(){

    while(~scanf("%d%d",&n,&k)){

    if(n>=k){

    printf("%d\n",n-k);

    }

    else {

    memset(vis,false,sizeof vis);

    memset(step,,sizeof step);

    bfs();

    printf("%d\n",step[k]);

    }

    }

    return ;

}

D - Fliptile（学到许多）

POJ - 3279

题意：给你一个01网格图，问你怎么按这些点，使得网格图全部置为0，找出字典序最小的方案；

解法：这题用到二进制思想，解法就是枚举第一行的按键，然后剩下的每一行都可以由上一行递推而来；

递推公式为：press[i][j]=(mp[i-1][j]+press[i-1][j]+press[i-1][j+1]+press[i-2][j]+press[i-1][j-1])&1;

最后判断一下情况是否符合，即最后一行按键是否能全部熄灭，

这里我犯了一个错误，就是判断最后一行时没有按照递推公式算导致错误；

然后枚举第一行的按键用到了二进制，即枚举0<i<(1<<m)，表示有m位二进制数，然后用位运算截取每一位数，即为 press[1][j]=(i>>(m-j))&1;

over

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using namespace std;

int mp[][],ans[][],press[][];

int n,m;

const int inf=0x3f3f3f3f;

int guess(){

    for(int i=;i<=n;i++){

    for(int j=;j<=m;j++){

    press[i][j]=(mp[i-][j]+press[i-][j]+press[i-][j+]+press[i-][j]+press[i-][j-])&;

    }

    }

    for(int j=;j<=m;j++){

    if((press[n][j]+mp[n][j]+

    press[n-][j]+press[n][j-]+press[n][j+])&!=)

    return inf;

    }

    int cnt=;

    for(int i=;i<=n;i++){

    for(int j=;j<=m;j++){

    cnt+=press[i][j];

    }

    }

    return cnt;

}

int main(){

    while(~scanf("%d%d",&n,&m)){

    memset(mp,,sizeof mp);

    memset(ans,,sizeof ans);

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

    scanf("%d",&mp[i][j]);

    int res=inf;

    for(int i=;i<(<<m);i++){

    memset(press,,sizeof press);

    int test=;

    for(int j=;j<=m;j++){

    press[][j]=(i>>(m-j))&;

    }

//    cout<<"test:"<<i<<" "<<guess()<<endl;

//    for(int i=1;i<=n;i++)

//    for(int j=1;j<=m;j++)

//    printf("%d%c",press[i][j],j==m?'\n':' ');

    int sum=guess();

    if(res>sum){

    res=sum;

    memcpy(ans,press,sizeof press);

    }

    }

    if(res==inf)printf("IMPOSSIBLE\n");

    else {

//        cout<<"test:"<<endl;

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

    printf("%d%c",ans[i][j],j==m?'\n':' ');

    }

    }

    return ;

}

E - Find The Multiple

POJ - 1426

题意：就是给你一个数，让你找它的一个只含01倍数的十进制数，

解法：直接深搜，但开始T了一发，没有做好剪树枝

计一个flag，如果搜到目标就停止；这样就能过了；

#include<cstdio>

using namespace std;

#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)

#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)

#define pb push_back

typedef long long ll;

typedef unsigned long long ull;

int n,flag;

ull ans;

void dfs(ull x,int step){

     if(flag)return ;

     if(x%n==){

     flag=;

     ans=x;

     return ;

     }

     if(step==)return ;

     dfs(x*+,step+);

     dfs(x*,step+);

}

int main(){

//    cout<<1000000000000000110%6<<endl;

    while(~scanf("%d",&n),n){

    ans=,flag=;

    dfs(*1ll,);

    printf("%lld\n",ans);

    }

    return ;

}

F - Prime Path

POJ - 3126

题意：就是给你两个素数，问你移动几步，使得由p走到q，而且每次移动只能变为素数，问你要变换几步；

解法：直接广搜即可；注意枚举每一位的情况；

#include<bits/stdc++.h>

#include<queue>

#include<cstring>

using namespace std;

#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)

#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)

#define pb push_back

#define fi first

#define se second

typedef long long ll;

typedef unsigned long long ull;

typedef long double ldb;

const int maxn=1e5+;

bool isprime[maxn];

void makeprime(){

     memset(isprime,true,sizeof isprime);

     isprime[]=;

     for(int i=;i*i<=maxn;i++){

     if(isprime[i]==)continue;

     for(int j=i*;j<=maxn;j+=i){

     isprime[j]=;

     }

     }

//     rep(i,1,maxn){

//     cout<<i<<" "<<isprime[i]<<endl;

//     }

}

struct point{int num,step;};

int ans,p,q;

bool vis[maxn];

bool  bfs(){

      memset(vis,,sizeof vis);

     vis[p]=;

     point tmp,next;

     tmp.num=p,tmp.step=;

     queue<point>Q;

     Q.push(tmp);

     while(!Q.empty()){

     tmp=Q.front();

     Q.pop();

     vis[tmp.num]=;

     if(tmp.num==q){

     ans=tmp.step;

     return true;

     }

     int t=tmp.num;

     for(int i=;i<;i++){

     for(int j=;j<=;j++){

     t=tmp.num;

     if(i==){

     t-=t%;

     t+=j;

     }

     else if(i==){

     t-=t%/*;

     t+=j*;

     }

     else if(i==){

     t-=t%/*;

     t+=j*;

     }

     else if(i==){

     t-=t%/*;

     t+=j*;

     }

     if(t==tmp.num||t<||vis[t]||!isprime[t])continue;

     next.num=t,next.step=tmp.step+;

     vis[t]=;

     Q.push(next);

     }

     }

     }

     return false;

}

int main(){

    makeprime();

    int cas;

    scanf("%d",&cas);

    while(cas--){

    memset(vis,,sizeof vis);

    scanf("%d %d",&p,&q);

    ans=;

    if(bfs())printf("%d\n",ans);

    else printf("Impossible\n"); 

    }

    return ;

}

G - Shuffle'm Up

POJ - 3087

题意：就是给你两堆牌，问你怎么洗才能洗到目标状态，如果洗不到，输出-1；

解法：模拟洗牌的过程，如果洗到初始的状态，说明洗不到，

这里我犯了一个错误，就是在在下标里面写位运算会出错，也不知tmp[i*2]=s2[i];道为什么；

tmp[i*2]=s2[i]; 写成tmp【i>.>1】就不对了

#include<iostream>

#include<string>

#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)

#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)

using namespace std;

typedef long long ll;

string tmp,s1,s2,s12,goal;

int step,n,ans;

void bfs(){

     s1=tmp.substr(,n);

     s2=tmp.substr(n,n);

     for(int i=;i<n;i++){

     tmp[i*]=s2[i];

     tmp[i*+]=s1[i];

     }

     step++;

     if(tmp.compare(goal)==){

     ans=step;

     return ;

     }

       if(tmp.compare(s12)==){

       ans=-;

       return ;

       }

     bfs();

}

int main(){

    int t,cas=;

//    scanf("%d",&t);

    cin>>t;

    while(t--){

//    scanf("%d",&n);

    cin>>n>>s1>>s2>>goal;

    tmp=s1+s2;

    s12=tmp;

    ans=step=;

    bfs();

    printf("%d %d\n",cas++,ans);

    }

    return ;

}

待更新；

PS：还是太菜了，要坚持刷题，写博客；

kuangbin专题——简单搜索的更多相关文章

kuangbin专题简单搜索题目几道题目
1.POJ1321棋盘问题 Description 在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别.要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形 ...
[kuangbin带你飞]专题一简单搜索题解报告
又重头开始刷kuangbin,有些题用了和以前不一样的思路解决.全部题解如下点击每道题的标题即可跳转至VJ题目页面. A-棋盘问题棋子不能摆在相同行和相同列,所以我们可以依此枚举每一行,然后标记每 ...
【算法系列学习三】[kuangbin带你飞]专题二搜索进阶之 A-Eight 反向bfs打表和康拓展开
[kuangbin带你飞]专题二搜索进阶之 A-Eight 这是一道经典的八数码问题.首先,简单介绍一下八数码问题: 八数码问题也称为九宫问题.在3×3的棋盘,摆有八个棋子,每个棋子上标有1至8的 ...
简单搜索 kuangbin C D
C - Catch That Cow POJ - 3278 我心态崩了,现在来回顾很早之前写的简单搜索,好难啊,我怎么写不出来. 我开始把这个写成了dfs,还写搓了... 慢慢来吧. 这个题目很明显是 ...
ElasticSearch 5学习(4)——简单搜索笔记
空搜索: GET /_search hits: total 总数 hits 前10条数据 hits 数组中的每个结果都包含_index._type和文档的_id字段,被加入到_source字段中这意味 ...
nyoj 284 坦克大战简单搜索
题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=284 题意:在一个给定图中,铁墙,河流不可走,砖墙走的话,多花费时间1,问从起点到终点至少 ...
分布式搜索ElasticSearch构建集群与简单搜索实例应用
分布式搜索ElasticSearch构建集群与简单搜索实例应用关于ElasticSearch不介绍了,直接说应用. 分布式ElasticSearch集群构建的方法. 1.通过在程序中创建一个嵌入es ...
solr简单搜索案例
solr简单搜索案例使用Solr实现电商网站中商品信息搜索功能,可以根据关键字搜索商品信息,根据商品分类.价格过滤搜索结果,也可以根据价格进行排序,实现分页. 架构分为: 1. solr服务器 2. ...
和我一起打造个简单搜索之SpringDataElasticSearch入门
网上大多通过 java 操作 es 使用的都是 TransportClient,而介绍使用 SpringDataElasticSearch 的文章相对比较少,笔者也是摸索了许久,接下来本文介绍 Spr ...

随机推荐

mapreduce 本地调试需要注意的问题
1.写好的程序直接在hadoop集群里面执行 2.如果需要在本地调试,需要注释掉mapred-site.xml <configuration> <!-- <property&g ...
Java设计模式-迭代子模式（Iterator）
顾名思义,迭代器模式就是顺序访问聚集中的对象,一般来说,集合中非常常见,如果对集合类比较熟悉的话,理解本模式会十分轻松.这句话包含两层意思:一是需要遍历的对象,即聚集对象,二是迭代器对象,用于对聚集对 ...
asp&period;net中virtual和abstract的区别
这篇文章主要介绍了asp.net中virtual和abstract的区别,较为详细的分析了virtual与abstract的概念与具体用法,并以实例的形式予以总结归纳,需要的朋友可以参考下本文实例分 ...
GIT GUI的使用(转)
前段时间跟着Ruby On Rails的toturial玩了一把Git,今天再回过头来,觉得这个版本控制工具真的很不错.下面来讲一下,在windows下如何通过git gui来管理代码. 首先,要在h ...
Less和Sass编译
使用koala编译 Koala 是一款由国人开发的开源预处理语言图形编译工具,目前已支持 Less.Sass.Compass 与CoffeeScript. 目前支持以下系统:Windows,Mac, ...
MySQL 加密/压缩函数
这些问题可能导致数据值的改变.一般而言,上述问题可能在你使用非二进制串数据类型(如char,varchar,text等数据类型)的情况下发生. AES_ENCRYPT()和AES_DECRYPT() ...
【android】android下的junit
<instrumentation android:name="android.test.InstrumentationTestRunner" android:targetPa ...
html 页面太长滚动时，固定页面菜单标签，或者导航标签的位置，fixed/stickUp the position
有时你曾经需要把页面上的某些东西当页面太长发滚动的时候保留置顶位置显示,或许你有别的实现方式,我这个仅供参考, 源代码: /*global $, jQuery, alert*/ (function ( ...
Selenium基础知识
本人博客文章网址:https://www.peretang.com/basic-knowledge-of-selenium/ 什么是Selenium Selenium是一个自动化测试工具是一组不同的 ...
FatMouse and Cheese
FatMouse and Cheese Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u ...