注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1429  

2012-07-18 16:43:59|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=1429

bfs+状态压缩,第一次做,值得研究学习

状态压缩:10个钥匙一共有1024种状态,搜索的时候需要记录每一步的状态

数组大小为10的bool数组,对应10种钥匙的状态,1表示找到,0表示为找到,

将该10种钥匙的状态按二进制计算成十进制的结果记录在变量key里,表示当前钥匙的状态

/*
 * fudq.cpp
 *
 *  Created on: 2012-07-18
 *      Author: fudq
 */
//bfs+状态压缩
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<iomanip>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<stack>
#include<vector>
#include<iostream>
using namespace std;
#define N 25
struct Node
{
 int x,y;
 int step,key;//key记录当前找到钥匙的状态
 bool flag[12];//对应10中钥匙的状态
};

char f[N][N];
bool mark[N][N][1100];//一共有1024种状态,记录搜索的路径和10种钥匙的状态
int dir[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int sx,sy,T,n,m;

void bfs()
{
 Node p,t;
 int i,temp,k;
 p.x=sx;p.y=sy;p.step=0;p.key=0;
 memset(p.flag,false,sizeof(p.flag));
 memset(mark,0,sizeof(mark));
 queue<Node>Q;
 Q.push(p);
 while(!Q.empty())
 {
  p=Q.front();
  Q.pop();
  if(f[p.x][p.y]=='^')
  {
   if(p.step>=T)
    printf("-1\n");
   else
    printf("%d\n",p.step);
   return ;
  }
  for(i=0;i<4;i++)
  {
   t=p;
   t.x+=dir[i][0];
   t.y+=dir[i][1];
   t.step++;
   if(f[t.x][t.y]=='*' || t.x<0 || t.x>=n || t.y<0 || t.y>=m)
    continue;
   if(f[t.x][t.y]<='j' && f[t.x][t.y]>='a')
   {
    k=f[t.x][t.y]-'a';
    if(t.flag[k])//更新当前钥匙的状态
     temp=t.key;
    else
     temp=t.key+(1<<k);//使用位运算的时候加上括号
    if(!mark[t.x][t.y][temp])
    {
     mark[t.x][t.y][temp]=true;
     t.key=temp;
     t.flag[k]=true;
     Q.push(t);
    }
   }
   else if(f[t.x][t.y]<='J' && f[t.x][t.y]>='A')
   {
    k=f[t.x][t.y]-'A';
    if(t.flag[k] && !mark[t.x][t.y][t.key])
    {
     mark[t.x][t.y][t.key]=true;
     Q.push(t);
    }
   }
   else if(f[t.x][t.y]=='.' || f[t.x][t.y]=='^')
   {
    if(!mark[t.x][t.y][t.key])
    {
     mark[t.x][t.y][t.key]=true;
     Q.push(t);
    }
   }
  }
 }
 printf("-1\n");
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("testin.txt","r",stdin);
#endif
    int i,j;
    while(scanf("%d%d%d",&n,&m,&T)!=EOF)
    {
     getchar();
     for(i=0;i<n;i++)
     {
      for(j=0;j<m;j++)
      {
       scanf("%c",&f[i][j]);
       if(f[i][j]=='@')
       {
        sx=i;
        sy=j;
        f[i][j]='.';
       }
      }
      getchar();
     }
     bfs();
    }
 return 0;
}

  评论这张
 
阅读(149)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018