fzu 2250 不可能弹幕结界 分析+模拟，考察思维严谨。
2024-09-28 10:15:37
Problem 2250 不可能弹幕结界 Accept: 5 Submit: 13
Time Limit: 1000 mSec Memory Limit : 65536 KB
Problem Description
咲夜需要穿过一片弹幕区，由于咲夜发动了符卡“The World”,所以弹幕是静止的。这片弹幕区以一个n*m的矩阵的形式给出。
‘.’表示这个位置是安全的，’x’表示这个位置上是有子弹的，禁止通行。咲夜每次能向左、右、下三个方向的相邻格子走，但是不能向上走。 同时由于时间有限，咲夜在进入每一行之后最多只能横向走k步。你可以简单地认为我们的目标就是从第0行走到第n+1行，起点和终点可以是在第0行和第n+1行的任意位置，当然第0行和第n+1行都是没有弹幕的。
然而这是号称不可能的弹幕结界，所以咲夜很可能无法穿过这片弹幕，所以咲夜准备了一个只能使用一次的技能，纵向穿越，她可以从任意位置直接穿越到另外任意一行的同一个位置(所在列不变)，当然她只能向下穿越，不能向上穿越。穿越的距离越远，耗费的资源自然越多，所以她想知道最短的穿越距离，才能使她成功通过这片弹幕区。
Input
输入包含多组数据。
对于每组数据：
第一行输入三个整数n,m,k,如上所述。
接下下输入一个n×m的矩阵，’.’表示当前这格没有子弹，是安全的，’x’表示这各有子弹，禁止通行。
N<=1000,k<=m<=1000
Output
对于每组数据输出一个整数，表示最短的穿越距离。
Sample Input
6 5 2 x.x.. ..xx. .xxx. xx.xx xx..x ..x.x 4 4 1 .xxx .xxx ...x xx.x
Sample Output
3 2
Hint
对于第一组样例，最优解是从第一行第二列走到第三行第一列，然后跳到第6行第一列，穿越距离为(6 – 3) = 3。
long long类型请用%I64d输出
Source
FOJ有奖月赛-2017年4月（校赛热身赛）
/**
题目：Problem 2250 不可能弹幕结界
链接：http://acm.fzu.edu.cn/problem.php?pid=2250
题意：看原题。
思路：
dtu[i][j]表示从底向上，不穿越能够到达的位置。
utd[i][j]表示从上到下，不穿越能够到达的位置。 然后枚举每一列，对每一列进行差值处理；取最小值。 */ #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+;
const double eps = 1e-;
char a[][];
int dtu[][];
int utd[][];
int lt[][], rt[][];
///预处理每个位置最左最右可达的地方。
int n, m, k;
void init()
{
memset(lt, -, sizeof lt);
memset(rt, -, sizeof rt);
for(int i = ; i <= n; i++){
for(int j = ; j <= m; j++){
if(a[i][j]=='.'){
lt[i][j] = lt[i][j-]+;
}
}
for(int j = m; j >= ; j--){
if(a[i][j]=='.'){
rt[i][j] = rt[i][j+]+;
}
}
}
}
int Min(int a,int b)
{
return a>b?b:a;
}
int Max(int a,int b)
{
return a>b?a:b;
}
void dfsdtu(int x,int y)
{
if(x==){
dtu[x][y] = ;
return ;
} dtu[x][y] = ;
if(a[x-][y]=='x') return ;
for(int i = Max(y-lt[x-][y],y-k); i <= Min(y+rt[x-][y],y+k); i++){
if(dtu[x-][i]) break;
dfsdtu(x-,i);
}
for(int i = Min(y+rt[x-][y],y+k); i >= Max(y-lt[x-][y],y-k); i--){
if(dtu[x-][i]) break;
dfsdtu(x-,i);
}
}
void dfsutd(int x,int y)
{
if(x==n){
utd[x][y] = ;
return ;
} utd[x][y] = ;
if(a[x+][y]=='x') return ;
for(int i = Max(y-k,y-lt[x+][y]); i <= Min(y+rt[x+][y],y+k); i++){
if(utd[x+][i]) break;
dfsutd(x+,i);
}
for(int i = Min(y+rt[x+][y],y+k); i >= Max(y-lt[x+][y],y-k); i--){
if(utd[x+][i]) break;
dfsutd(x+,i);
}
}
int main()
{
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
for(int i = ; i<= n; i++){
scanf("%s",a[i]+);
}
init();
memset(dtu, , sizeof dtu);
memset(utd, , sizeof utd);
for(int i = ; i <= m; i++){
if(a[n][i]=='.'){
dfsdtu(n,i);//由底向上
}
}
for(int i = ; i <= m; i++){
if(a[][i]=='.'){
dfsutd(,i);//由上到下
}
} int ans = n+;
for(int i = ; i <= m; i++){
int dt = n+, ut = ;
for(int j = ; j <= n; j++){
if(dtu[j][i]){
dt = j;
}
if(utd[j][i]){
ut = j;
}
if(dt>ut){
ans = Min(ans,dt-ut);
}
ans = Min(ans,dt);
ans = Min(ans,n+-ut);
if(dt==||ut==n) ans = ;
} }
printf("%d\n",ans);
}
return ;
}
最新文章
- EF 二级缓存 EFSecondLevelCache
- border：none 和border：0区别差异
- 日志解析LogParse启动参数配置
- java内省机制及PropertyUtils使用方法
- 怎样关闭google的自动更新
- 超简单的NDK单步调试方法
- unity2d之2d帧动画创建
- 数据库E-R模型，数据字典
- DataGridView自动行号
- 解决rsync 同步auth failed on module问题
- flume【源码分析】分析Flume的拦截器
- 标准SVD和改进的SVD
- Python判断文件是否存在的三种方法
- Python---socket库
- springboot2 pagehelper 使用笔记
- 20190219备份 java spring boot 学习链接（日／英）
- PXE无人值守安装
- VM for Linux 版本的Bundle格式文件的安装
- 解决com.mysql.jdbc.PacketTooBigException: Packet for query is too large
- 《课程设计》——cupp的使用