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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 2757  

2012-07-20 21:49:14|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这题可以用BFS+优先队列解决,也可以不用优先队列,不用优先队列的话,需要主要的是:先把不花时间的先进队列,然后再考虑需要话费时间的,这样做也就达到了使用优先队列的目地
开始做的时候没有用优先队列,只用了390MS,代码如下:
后面贴上用优先队列做的代码,用了1750MS

/*
* fudq.cpp
*
* Created on: 2012-07-19
* Author: fudq
*/
#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<iostream>
using namespace std;
#define N 1005
struct Node
{
int x,y,step;
};
int n,m,sa,sb,ea,eb;
int dir[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
char f[N][N];
bool vis[N][N];
queue<Node>Q;

void bfs()
{
while(!Q.empty())
Q.pop();
int i,j;
Node p,t,tmp;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
vis[i][j]=false;
vis[sa][sb]=true;
p.x=sa;p.y=sb;p.step=0;
Q.push(p);
while(!Q.empty())
{
p=Q.front();
Q.pop();
if(p.x==ea && p.y==eb)
{
printf("%d\n",p.step);
return ;
}
tmp=p;
while(1)
{
t.x=tmp.x+dir[f[tmp.x][tmp.y]-'0'][0];
t.y=tmp.y+dir[f[tmp.x][tmp.y]-'0'][1];
if(t.x>=0 && t.x<n && t.y>=0 && t.y<m && !vis[t.x][t.y])
{
t.step=tmp.step;
if(t.x==ea && t.y==eb)
{
printf("%d\n",t.step);
return ;
}
vis[t.x][t.y]=true;
Q.push(t);
tmp=t;
}
else
break;
}
for(i=0;i<8;i++)
{
t.x=p.x+dir[i][0];
t.y=p.y+dir[i][1];
if(t.x>=0 && t.x<n && t.y>=0 && t.y<m && !vis[t.x][t.y])
{
if(f[p.x][p.y]-'0'==i)
t.step=p.step;
else
t.step=p.step+1;
if(t.x==ea && t.y==eb)
{
printf("%d\n",t.step);
return ;
}
vis[t.x][t.y]=true;
Q.push(t);
tmp=t;
while(1)
{
t.x=tmp.x+dir[f[tmp.x][tmp.y]-'0'][0];
t.y=tmp.y+dir[f[tmp.x][tmp.y]-'0'][1];
if(t.x>=0 && t.x<n && t.y>=0 && t.y<m && !vis[t.x][t.y])
{
t.step=tmp.step;
if(t.x==ea && t.y==eb)
{
printf("%d\n",t.step);
return ;
}
vis[t.x][t.y]=true;
Q.push(t);
tmp=t;
}
else
break;
}
}
}
}
printf("0\n");
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
#endif
int t,i;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<n;i++)
scanf("%s",f[i]);
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d",&sa,&sb,&ea,&eb);
if(sa==sb && ea==eb)
{
printf("0\n");
continue;
}
sa--;sb--;ea--;eb--;
bfs();
}
}
return 0;
}


用优先队列做的代码:

/*
* fudq.cpp
*
* Created on: 2012-07-19
* Author: fudq
*/
#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<iostream>
using namespace std;
#define N 1005
struct Node
{
int x,y,step;
friend bool operator < (Node a,Node b)
{
return a.step>b.step;
}
};
int n,m,sa,sb,ea,eb;
int dir[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
char f[N][N];
int dis[N][N];

void bfs()
{
int i,j;
Node p,t;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
dis[i][j]=INT_MAX;
dis[sa][sb]=0;
p.x=sa;p.y=sb;p.step=0;
priority_queue<Node>Q;
Q.push(p);
while(!Q.empty())
{
p=Q.top();
Q.pop();
if(p.x==ea && p.y==eb)
{
printf("%d\n",p.step);
return ;
}
for(i=0;i<8;i++)
{
t.x=p.x+dir[i][0];
t.y=p.y+dir[i][1];
if(t.x>=0 && t.x<n && t.y>=0 && t.y<m)
{
if(f[p.x][p.y]-'0'==i)
t.step=p.step;
else
t.step=p.step+1;
if(t.step<dis[t.x][t.y])
{
dis[t.x][t.y]=t.step;
Q.push(t);
}
}
}
}
printf("0\n");
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
#endif
int t,i;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<n;i++)
scanf("%s",f[i]);
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d",&sa,&sb,&ea,&eb);
if(sa==ea && sb==eb)
{
printf("0\n");
continue;
}
sa--;sb--;ea--;eb--;
bfs();
}
}
return 0;
}



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

历史上的今天

评论

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

页脚

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