题目链接:https://www.nowcoder.com/acm/contest/105/F

解题思路:这道题第一眼直接思路就是搜索,但想了半天没想到有什么好办法搜,然后就转成最短路写了,

因为多入口和出口,建立一个汇点一个源点,权值自己设,然后上下左右能相连的权值为1,传送阵(能用的前提下)入口和出口两个点的权值设为3;

然后就是最短路;

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
#define maxn 400005
#define inf 0x3f3f3f3f
using namespace std;
struct Edge
{
int next;
int to;
int w;
}edge[maxn];
struct node
{
int num;
int dist;
node(int _num=0,int _dist=0):num(_num),dist(_dist){}
friend bool operator<(node a,node b)
{
return a.dist>b.dist;
}
};
int head[maxn];
int cnt;
int dist[maxn];
int visit[maxn];
int ans[maxn];
void add(int u,int v,int w)
{
edge[cnt].next=head[u];
edge[cnt].to=v;
edge[cnt].w=w;
head[u]=cnt++;
}
void dij(int u)
{
priority_queue<node>q;
memset(dist,inf,sizeof(dist));
memset(visit,0,sizeof(visit));
dist[u]=0;
q.push(node(u,0));
while(!q.empty())
{
node p=q.top();
q.pop();
int now=p.num;
for(int i=head[now];i!=-1;i=edge[i].next)
{
Edge e=edge[i];
if(dist[e.to]>dist[now]+e.w)
{
dist[e.to]=dist[now]+e.w;
q.push(node(e.to,dist[e.to]));
}
}
}
}
int main()
{
int n,m,q;
int x,y,w;
int tx,ty,ex,ey;
int cot=0;
char s[500][500];
while(cin>>n>>m>>q)
{
cot=cnt=0;
memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>s[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(s[i][j]!='#')
{
if(s[i+1][j]!='#'&&i+1<=n)
{
x=(i-1)*m+j;y=(i)*m+j;add(x,y,1);
}
if(s[i-1][j]!='#'&&i-1>=1)
{
x=(i-1)*m+j;y=(i-2)*m+j;add(x,y,1);
}
if(s[i][j+1]!='#'&&(j+1)<=m)
{
x=(i-1)*m+j;y=(i-1)*m+j+1;add(x,y,1);
}
if(s[i][j-1]!='#'&&(j-1)>=1)
{
x=(i-1)*m+j;y=(i-1)*m+j-1;add(x,y,1);
}
}
if(s[i][j]=='S')
{
x=0;y=(i-1)*m+j;add(x,y,1);
}
if(s[i][j]=='T')
{
ans[++cot]=(i-1)*m+j;
}
}
while(q--)
{
cin>>tx>>ty>>ex>>ey;
tx++;ty++;ex++;ey++;
if(s[tx][ty]!='#'&&s[ex][ey]!='#')
{
x=(tx-1)*m+ty;y=(ex-1)*m+ey;
add(x,y,3);
}
}
dij(0);
int a=inf;
for(int i=1;i<=cot;i++)
{
a=min(a,dist[ans[i]]);
}
if(a==inf)
cout<<"-1\n";
else
cout<<a-1<<endl;
}
}

  

最新文章

  1. Express 教程 01 - 入门教程之经典的Hello World
  2. Struts2中的Unable to load configuration错误的分析与解决方法
  3. android:layout_gravity 和 android:gravity 的区别
  4. 【转】 深入main函数中的参数argc,argv的使用详解
  5. Atitit..文件上传组件选型and最佳实践总结(3)----断点续传控件的实现
  6. UIVisualEffectView为视图添加特殊效果
  7. Android应用资源--之属性(Attribute)资源
  8. LiBsvm用于多分类时训练模型参数含义
  9. 【小程序开发】微信小程序开发中遇到的那些坑...
  10. pyqt lineedit右边显示按钮效果
  11. centos minimal Bind 主从服务器部署
  12. 关于jsp页面加载时报错500的问题
  13. [Active Learning] Multi-Criteria-based Active Learning
  14. 【python】md5加密方法相关使用
  15. 【开源GPS追踪】 之 服务器端opengts安装
  16. dubbo 异步回调
  17. Ext JS 4 的类系统
  18. Redis脚本
  19. Git 环境设置(安装)
  20. node.js发送邮件email

热门文章

  1. keystone系列三:网关协议
  2. 蓝牙BLE设备主机重启回连流程分析
  3. 命令行创建mysql数据库指定编码方法
  4. Deno下一代Nodejs?Deno初体验
  5. Windows 10 配置Linux及安装Docker
  6. 朱晔的互联网架构实践心得S1E10:数据的权衡和折腾【系列完】
  7. springboot 双数据源+aop动态切换
  8. sqlserver笔记
  9. js在微信、微博、QQ、Safari唤起App的解决方案
  10. mysql_linux(centos7 mysql 5.7.19)