Chamber of Secrets
题目连接:
http://codeforces.com/problemset/problem/173/B
Description
"The Chamber of Secrets has been opened again" — this news has spread all around Hogwarts and some of the students have been petrified due to seeing the basilisk. Dumbledore got fired and now Harry is trying to enter the Chamber of Secrets. These aren't good news for Lord Voldemort. The problem is, he doesn't want anybody to be able to enter the chamber. The Dark Lord is going to be busy sucking life out of Ginny.
The Chamber of Secrets is an n × m rectangular grid in which some of the cells are columns. A light ray (and a basilisk's gaze) passes through the columns without changing its direction. But with some spell we can make a column magic to reflect the light ray (or the gaze) in all four directions when it receives the ray. This is shown in the figure below.
The left light ray passes through a regular column, and the right ray — through the magic column.
The basilisk is located at the right side of the lower right cell of the grid and is looking to the left (in the direction of the lower left cell). According to the legend, anyone who meets a basilisk's gaze directly dies immediately. But if someone meets a basilisk's gaze through a column, this person will get petrified. We know that the door to the Chamber is located on the left side of the upper left corner of the grid and anyone who wants to enter will look in the direction of its movement (in the direction of the upper right cell) from that position.
This figure illustrates the first sample test.
Given the dimensions of the chamber and the location of regular columns, Lord Voldemort has asked you to find the minimum number of columns that we need to make magic so that anyone who wants to enter the chamber would be petrified or just declare that it's impossible to secure the chamber.
Input
The first line of the input contains two integer numbers n and m (2 ≤ n, m ≤ 1000). Each of the next n lines contains m characters. Each character is either "." or "#" and represents one cell of the Chamber grid. It's "." if the corresponding cell is empty and "#" if it's a regular column.
Output
Print the minimum number of columns to make magic or -1 if it's impossible to do.
Sample Input
3 3
.#.
...
.#.
Sample Output
2
Hint
题意
给你一个n*m的矩阵,你从(1,0)位置射出一个平行于x轴的光,遇到#号的时候,你可以选择转弯
然后你要要到达(n,m+1)这个位置
问你最少用多少个#
题解:
直接spfa就可以过
你可以把这个图优化成二分图
然后再跑spfa
代码
#include<bits/stdc++.h>
using namespace std;
vector<int>H[1200];
vector<int>L[1200];
int d[1200][3];
int vis[1200][3];
int n,m;
char str[1200][1200];
struct node
{
int x,y;
};
void bfs(int x,int y)
{
queue<node> Q;
for(int i=0;i<1200;i++)
for(int j=0;j<3;j++)
d[i][j]=1e9;
node now;
now.x=x,now.y=y;
d[now.x][now.y]=0;
vis[now.x][now.y]=1;
Q.push(now);
while(!Q.empty())
{
now = Q.front();
Q.pop();
vis[now.x][now.y]=0;
if(now.y==0)
{
for(int i=0;i<H[now.x].size();i++)
{
node next = now;
next.y = 1;
next.x = H[now.x][i];
if(d[next.x][next.y]>d[now.x][now.y]+1)
{
d[next.x][next.y]=d[now.x][now.y]+1;
if(vis[next.x][next.y])continue;
vis[next.x][next.y]=1;
Q.push(next);
}
}
}
if(now.y==1)
{
for(int i=0;i<L[now.x].size();i++)
{
node next = now;
next.y = 0;
next.x = L[now.x][i];
if(d[next.x][next.y]>d[now.x][now.y]+1)
{
d[next.x][next.y]=d[now.x][now.y]+1;
if(vis[next.x][next.y])continue;
Q.push(next);
}
}
}
}
if(d[n][0]>1e8)
printf("-1\n");
else
printf("%d\n",d[n][0]);
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",str[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(str[i][j]=='#')
H[i].push_back(j),L[j].push_back(i);
bfs(1,0);
}
CodeForces 173B Chamber of Secrets spfa的更多相关文章
-
CodeForces 173B Chamber of Secrets 二分图+最短路
题目链接: http://codeforces.com/problemset/problem/173/B 题意: 给你一个n*m的地图,现在有一束激光从左上角往左边射出,每遇到‘#’,你可以选择光线往 ...
-
CodeForces 173B Chamber of Secrets (二分图+BFS)
题意:给定上一个n*m的矩阵,你从(1,1)这个位置发出水平向的光,碰到#可以选择四个方向同时发光,或者直接穿过去, 问你用最少的#使得光能够到达 (n,m)并且方向水平向右. 析:很明显的一个最短路 ...
-
Codeforces 689B. Mike and Shortcuts SPFA/搜索
B. Mike and Shortcuts time limit per test: 3 seconds memory limit per test: 256 megabytes input: sta ...
-
Codeforces Gym 100269D Dwarf Tower spfa
Dwarf Tower 题目连接: http://codeforces.com/gym/100269/attachments Description Little Vasya is playing a ...
-
Codeforces 786B. Legacy 线段树+spfa
题目大意: 给定一个\(n\)的点的图.求\(s\)到所有点的最短路 边的给定方式有三种: \(u \to v\) \(u \to [l,r]\) \([l,r] \to v\) 设\(q\)为给定边 ...
-
【CF173B】Chamber of Secrets(二分图,最短路)
题意:给你一个n*m的地图,现在有一束激光从左上角往右边射出,每遇到‘#’,你可以选择光线往四个方向射出,或者什么都不做,问最少需要多少个‘#’往四个方向射出才能使关系在n行往右边射出. 思路:将每一 ...
-
Codeforces 346D Robot Control DP spfa 01BFS
题意及思路:https://www.cnblogs.com/zjp-shadow/p/9562888.html 这题由于性质特殊,可以用01BFS来进行DP的转移. 代码: #include < ...
-
配置魔药 [NOIP模拟] [DP] [费用流]
问题描述在<Harry Potter and the Chamber of Secrets>中,Ron 的魔杖因为坐他老爸的 Flying Car 撞到了打人柳,不幸被打断了,从此之后,他 ...
-
Harry Potter
Names appearing in "Harry Potter" 1.Harry Potter ①Harry is from Henry. ②Harry is related t ...
随机推荐
-
nodejs的第五天学习笔记
一.调试nodejs代码 1)使用console.log() 使用麻烦,用了以后还要删除 2)nodejs的自带调试器 -node debug a.js 没有任何作用,一个玩具,将来有一天可以会变得强 ...
-
如何搭建lamp(CentOS7+Apache+MySQL+PHP)环境 [转]
在网上搜资料,自己在本地虚拟机上尝试搭建,弄了整整一天一夜,终于弄好了.网上的资料,虽然很多,但大多都是重复的,拿去试了之后,又很多都不能得到正确的结果.最终找到了适合我的linux环境的搭建方式;在 ...
-
【openGL】关于画点
#include "stdafx.h" #include <GL/glut.h> #include <stdlib.h> #include <math ...
-
MySQL学习基础 之 起航篇
MySQL 学习来自慕课网<与MySQL的零距离接触> MySQL是一个开源的关系型数据库管理系统 MySQL分为社区版和企业版 MySQL登录和退出相关的命令 参数 描述 -D,--da ...
-
【MySQL】ERROR 1045 (28000): Access denied for user的解决方法
去官网下载压缩版的MySQL Server,解压配置path环境变量后.然后克隆my-default.ini创建my.ini文件,在文件中[mysqld]下面配置basedir和datadir bas ...
-
[Head First Python]5. 推导数据:处理数据
读取4个文件内容,格式化数据,升序,显示每个文件前3个数据 julie.txt 2.59,2.11,2:11,2:23,3-10,2-23,3:10,3.21,3-21 james.txt 2-34, ...
-
php unset 数组陷阱
我们删除一个array, unset($arr); 想删除某个元素 unsert($arr[i]) 一个陷阱是: unset() 函数允许删除数组中的某个键.但要注意数组将不会重建索引.如果需要删除后 ...
-
[UE4]让箭头保持水平
如图所示,当手柄前后左右转动的时候,箭头也会跟着转动,我们的目标是要求箭头紧贴着地面,不会跟着手柄前后左右转动. 分析上图坐标系可以知道,只要让箭头绕着Z轴转动就可以了,不需要绕着X轴和Y轴旋转.
-
Python档案袋( Sys 与 Import 模块)
Sys模块: 获取Python有关的环境变量: import sys #得到Python的一些相关路径,环境变量 #其中site-packages目录存放的是一些第三方库 #其中lib目录存放的是一些 ...
-
第四篇、Python文件处理
1.文件操作 1) 文件操作流程 a. 打开文件,得到文件句柄并赋值给一个变量 b. 通过句柄对文件进行操作 c. 关闭文件 f=open('a.txt','r',encoding='utf-8') ...