笨笨鸟
笨笨鸟
题目描述GM下载了一款流行手机游戏“笨笨鸟”，主角笨笨鸟在一个10行N列的方格中移动，一开始笨笨鸟在左下角的方格中心，作为起点准备出发，若GM不做任何操作，笨笨鸟将一直向右以1秒1格的速度移动，若按下手机屏幕，笨笨鸟将起飞，以右上45度飞翔，一旦按下手机屏幕的手指松开，笨笨鸟将以右下45度滑翔。值得注意的是，到了顶行依然按下不松手，笨笨鸟将向右1秒1格移动，GM不怎么会玩游戏，请帮助他让笨笨鸟成为不死鸟（即不触碰障碍物顺利通过N列）。
输入格式第一行输入包含整数N(1≤N≤1e5 )。表示场地有多少列。
接下来10行中的每一行包含N个字符。字符是. 或者X ，表示游戏中场地的布局，字符X表示障碍物， . 表示可以走的地方。所有输入数据保证有解。
输出格式第一行输出必须包含整数P（0≤P≤5∗1e4 )。表示GM按下按钮的次数 。
接下来 P行，每行输出一次操作，以达到通关游戏的目的。
每次操作由两个整数ti和xi决定，其中ti表示本次操作按下按钮的开始时间，xi表示本次操作按下按钮的持续时间。
所有操作必须按时间顺序进行排序。换句话说ti+xi≤ti+1。此外，在游戏结束后不应该有操作开始，即ti<N。
如果存在多个解决方案，则输出任意一个。本题答案已经写了SPJ。
分数分布：无特殊分数分布。
样例输入20
X..................X
.X................X.
..X..............X..
...X............X...
....X..........X....
.....X........X.....
......X......X......
.......X....X.......
........X..X........
.........XX.........
样例输出1
8 10
本题是一道模拟加dp的题，用dp[i,j]来表示是否可以到达[i,j]这个格子，顺便记录下上一个节点的状况
dp[i][j] dp[i+1][j-1]|dp[i][j-1] (i==0)
dp[i+1][j-1]|dp[i-1][j-1] (0<i<9)
dp[i-1][j-1]|dp[i][j-1] (i==9)
把整个图遍历一遍就行了
源码#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
int n;bool pr[100005];
int tot,begn[50005],last[50005];
char maze[15][100005];
bool dp[15][100005];int pre[15][100005];
void read(int &x)
{
int f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
x*=f;
}
void print(int sx,int sy)
{
if(sy<=0) return ;
print(pre[sx][sy],sy-1);
if(sx==pre[sx][sy]+1||(sx==9&&pre[sx][sy]==9)) pr[sy]=0;
if(sx==pre[sx][sy]-1||(sx==0&&pre[sx][sy]==0)) pr[sy]=1;
if(pr[sy]&&!pr[sy-1])
tot++,last[tot]=0,begn[tot]=sy;
if(pr[sy]) last[tot]++;
}
int main()
{
scanf("%d",&n);
for(int i=0;i<10;i++)
{
scanf("n");
for(int j=0;j<n;j++)
scanf("%c",&maze[i][j]);
}
dp[9][0]=1;
for(int j=1;j<n;j++)
for(int i=9;i>=0;i--)
{
if(maze[i][j]=='X') continue;
if(i==9)
if(dp[i][j-1])
dp[i][j]=1,pre[i][j]=i;
if(i==0)
if(dp[i][j-1])
dp[i][j]=1,pre[i][j]=i;
if(i>0)
if(dp[i-1][j-1])
dp[i][j]=1,pre[i][j]=i-1;
if(i<9)
if(dp[i+1][j-1])
dp[i][j]=1,pre[i][j]=i+1;
}
for(int i=0;i<10;i++)
if(dp[i][n-1])
{
print(i,n-1);
printf("%dn",tot);
for(int j=1;j<=tot;j++)
printf("%d %dn",begn[j],last[j]);
return 0;
}
return 0;
}
谢谢阅读！！！
相关知识
廊坊笨笨牛宠物用品有限公司
阿笨猫传电子宠物声音免费在线播放
给笨尼换了新的狗粮@BlueBuffalo宠物食品 ，看测评蛋白质达到34%
原创 养狗忠告：狗狗有这些表现，说明是“笨狗”，养得心累
怎么看猫聪明还是笨，测试一下你家猫咪是笨蛋猫吗？
狗子们真的比猫咪笨吗？猫狗到底谁更聪明呢？
怎么挑选一只让自己满意的鹦鹉
“为啥我家狗这么笨，扔球都不捡？”狗：呵呵，你行你上！
哈士奇是笨狗吗？有人却把它训练成了救援犬，太不可思议了
在，上笨的狗是十大低智商宠物狗，哈士奇不在其中
网址: 笨笨鸟 https://m.mcbbbk.com/newsview158437.html
| 上一篇: 【Java】继承法——猫狗动物类 |
下一篇: 剑三跟宠怎么获得 |
