美文网首页
uva1601 bfs+地址编码

uva1601 bfs+地址编码

作者: Amosasas | 来源:发表于2017-10-07 11:46 被阅读0次

bfs还是很好写的,都是套路,但是所有的这类题问题在于怎么去在搜索中表达状态,无论是八数码把坐标射到一个数组,还是这道题把地址弄到一个int中去折腾,或者是倒水问题三个杯子数字,都是这个套路。我们无非要考虑这几个问题:1、用什么表达每次搜索时的状态 2、用这个状态表示方法怎么扩展节点3、扩展出来的节点用什么结构去记录(结点查找表:直接映射、哈希)
最开始我是用直接坐标表示的,空间大而且每次查找耗时巨大,就挂了。。。
这是网上找来的方法。。。
我会用双向bfs和A-star重新写一次。。。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int maxn=150,maxs=20;
const int dx[]={-1,1,0,0,0};
const int dy[]={0,0,1,-1,0};
inline int ID(int a,int b,int c)
{
    return (a<<16)|(b<<8)|c;
}
int s[3],t[3]; //保存初末状态
int deg[maxn];//某个格子有多少个相连的格子 
int G[maxn][5];//保存某个格子可以用到哪些格子
inline bool conflict(int a,int b,int a2,int b2)
{
    return a2==b2||(a2==b&&b2==a); //如果两个鬼移动到同一个位置或者位置互换则冲突
}
int d[maxn][maxn][maxn]; //走到某个状态经过的步数
int bfs()
{
    queue<int> q;
    memset(d,-1,sizeof(d));
    q.push(ID(s[0],s[1],s[2])); //每个状态给他编号来判断是否访问过
    d[s[0]][s[1]][s[2]]=0;
    while(!q.empty()){
        int u=q.front();q.pop();
        int a=(u>>16)&0xff,b=(u>>8)&0xff,c=u&0xff;
     //   cout<<a<<"   "<<b<<"    "<<c<<endl;
        if(a==t[0]&&b==t[1]&&c==t[2])return d[a][b][c];
        for(int i=0;i<deg[a];i++){
            int a2=G[a][i];
            for(int j=0;j<deg[b];j++){
                int b2=G[b][j];
                if(conflict(a,b,a2,b2))continue;
                for(int k=0;k<deg[c];k++){
                    int c2=G[c][k];
                    if(conflict(a,c,a2,c2))continue;
                    if(conflict(b,c,b2,c2))continue;
                    if(d[a2][b2][c2]!=-1)continue;
                    d[a2][b2][c2]=d[a][b][c]+1;
                    q.push(ID(a2,b2,c2));
                }
            }
        }
    }
    return -1;
}
int main()
{
    int w,h,n;
    char ch;
    //freopen("f.txt","r",stdin);
    while(scanf("%d%d%d\n",&w,&h,&n)==3&&n){
        char maze[20][20];
        for(int i=0;i<h;i++){
          for(int j = 0; j < w; j++) scanf("%c", &maze[i][j]);
          scanf("%c", &ch);
        }
          
         
        int cnt,x[maxn],y[maxn],id[maxn][maxn];
        cnt=0;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(maze[i][j]!='#'){  //把障碍去掉,建图
                    x[cnt]=i,y[cnt]=j,id[i][j]=cnt;
                    if(islower(maze[i][j]))s[maze[i][j]-'a']=cnt;
                    else if(isupper(maze[i][j]))t[maze[i][j]-'A']=cnt;
                    cnt++;
                }
            }
        }
        for(int i=0;i<cnt;i++){
            deg[i]=0;
            for(int dir=0;dir<5;dir++){
                int nx=x[i]+dx[dir],ny=y[i]+dy[dir];
                if(maze[nx][ny]!='#')G[i][deg[i]++]=id[nx][ny];//统计出每个位置可以移动到的位置
            }
        }
        //n==1||n==2时,把格子加上,凑够三个,初末位置重合
        if(n<=2){
            deg[cnt]=1;G[cnt][0]=cnt;s[2]=t[2]=cnt++;
        }
        if(n<=1){
            deg[cnt]=1;G[cnt][0]=cnt;s[1]=t[1]=cnt++;
        }
        printf("%d\n",bfs());

    }
}

相关文章

  • uva1601 bfs+地址编码

    bfs还是很好写的,都是套路,但是所有的这类题问题在于怎么去在搜索中表达状态,无论是八数码把坐标射到一个数组,还是...

  • python编码地址

    编码地址 https://docs.python.org/3/library/codecs.html#standa...

  • 地图和定位(三)

    一、地理编码和反地理编码 地理编码:把地址转为经纬度反地理编码:把经纬度转为地址 二、获取当前城市名称(定位+反地...

  • 高德地图 JS API 学习摘要6

    地理编码 地址 -> 坐标 Geocoder.getLocation,使用地理编码接口,根据地址转获取经纬度位置。...

  • iOS地址批量编码

  • 地址编码的转换

    问题 遇到一个与地址相关的问题:新生成的合约地址本质上与其它地址一样,都是 32 字节的byte数组;但是,当试图...

  • 逆向地址编码

    AMap.Geocoder is not a constructor 按坑爹的高德这个实例代码,报这个错误。 在前...

  • redis-API-哈希

    文档地址 内部编码 ziplist(压缩列表) hashtable(哈希表) 编码的选择 内部编码默认是zipli...

  • urllib.error

    地址栏错误 编码错误

  • 加载带汉字的URL时无法读取显示问题

    这时需要对地址进行编码。

网友评论

      本文标题:uva1601 bfs+地址编码

      本文链接:https://www.haomeiwen.com/subject/lzfjyxtx.html