2547 东方辉针城

时间限制: 1 s

空间限制: 32000 KB

题目等级 : 黄金 Gold

题目描述 Description

将于5月26日发售的东方辉针城在东方吧中引起了很多关注...

这个游戏是这样的，需要你操控一名角色，去和其他的杂鱼和boss决战。而对方和你的攻击的手段都是弹幕。在游戏中，你需要躲避他人的弹幕，并发射出自己的弹幕来攻击对方。本题中，为简单起见，只考虑对方发射的弹幕。

假设主角始终处于画面低端，将每秒与主角出现在一排的弹幕进行叠加，总共游戏进行了T秒，可以形成一个(T+1)×WIDTH大小的字符矩阵，“.”表示该点为空，“*”表示该点有至少一颗子弹。

现在告诉你主角的初始位置，求能否不中弹经过这T秒的弹幕，和操作的步骤。（主角不会⑨的）

题目认为抵达最后一行即视为通过，如果有多种不同的选择可以抵达最后一行请优先向左，其次不动，最后向右；题目保证数据合法且初始位置无弹幕。

输入描述 Input Description

输入数据包括T+3行。
第1行为两个正整数T和WIDTH，分表表示游戏进行的时间和屏幕的宽度。
第2行为一个正整数S，为初始的位置。
第3～T+3行每行包括WIDTH个字符，表示该点的状态。

输出描述 Output Description

第1行为一个字符串“Yes”或者“No”。表示能否不中弹通过此区域。
第2行为一个字符串，如果出现中弹则不输出。表示通过T秒的操作，“L”表示向左移动一个格子，“R”表示向右移动一个格子，“N”表示不动。

样例输入 Sample Input

8 5
3
.....
.....
*.*.*
*.*.*
*.*.*
*.*.*
***.*
.....
.....

样例输出 Sample Output

Yes
NRNNNNLL

数据范围及提示 Data Size & Hint

1≤T≤1000, 1≤WIDTH≤100

来自其他OJ, 简单题

分类标签 Tags 点此展开

/*
不知道为什么不对
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 1005
int move[N],a[]={-1,0,1};
int t,w,p,flag;
char map[N][N];
void out(){
    if(flag)
        for(int i=1;i<=t;i++){
            if(move[i]==-1) cout<<"L";
            else if(move[i]==0) cout<<"N";
            else if(move[i]==1) cout<<"R";
        }
    else
        cout<<"No"<<endl;
}
void dfs(int n,int s){
    if(n>t){flag=1;cout<<"Yes"<<endl;out();exit(0);}
    else if(map[n][s]=='.')
        for(int i=0;i<3;i++)
            if(map[n+1][s+a[i]]=='.')
                move[n]=a[i],
                dfs(n+1,s+a[i]);
}
int main(){
    cin>>t>>w>>p;
    for(int i=1;i<=t+1;i++)
        for(int j=1;j<=w;j++)
            cin>>map[i][j];
    dfs(1,p);
    return 0;
}

然后这样就A了

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 1005
int move[N],a[]={-1,0,1};
int t,w,p,flag;
char map[N][N];
void dfs(int n,int s){
    if(n>t){flag=1;cout<<"Yes"<<endl;}
    else if(map[n][s]=='.'){
        for(int i=0;i<3;i++){
            if(map[n+1][s+a[i]]=='.'){
                move[n]=a[i];
                dfs(n+1,s+a[i]);    
            }
            if(flag) return ;    
        }
    }
    else return ;        
}
int main(){
    cin>>t>>w>>p;
    for(int i=1;i<=t+1;i++)
        for(int j=1;j<=w;j++)
            cin>>map[i][j];
    dfs(1,p);
    if(flag)
        for(int i=1;i<=t;i++){
            if(move[i]==-1) cout<<"L";
            else if(move[i]==0) cout<<"N";
            else if(move[i]==1) cout<<"R";
        }
    else
        cout<<"No"<<endl;
    return 0;
}