51Nod 1572 宝岛地图

题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1572

题意:略。

思路:直接暴力判断的话会有两个点TLE挂掉,所以我们先预处理出所有可移动的点4个方向移动的最大距离,然后再去判断。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define MOD 1e9+7
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1000+5;
const int maxm=1e5+5;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
template<typename T> inline T gcd(T&a,T&b){return b==0?a:gcd(b,a%b);}
template<typename T> inline T lcm(T&a,T&b){return a/gcd(a,b)*b;}
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
struct Node{
    char s[2];
    int x;
}ins[maxm];
int n,m,q;
char maze[maxn][maxn];
int dp[4][maxn][maxn];
vector<pair<int,int> >vec;
vector<char>v;
int main(){
    read(n),read(m);
    for (int i=1;i<=n;i++){
        scanf("%s",maze[i]+1);
        for (int j=1;j<=m;j++){
            if (maze[i][j]>='A' && maze[i][j]<='Z'){
                vec.push_back(make_pair(i,j));
            }
        }
    }
    read(q);
    for (int i=1;i<=q;i++){
        scanf("%s%d",ins[i].s,&ins[i].x);
    }
    memset(dp,-1,sizeof(dp));
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (maze[i][j]!='#'){
                dp[0][i][j]=dp[0][i-1][j]+1;
                dp[1][i][j]=dp[1][i][j-1]+1;
            }
        }
    }
    for (int i=n;i>=1;i--){
        for (int j=m;j>=1;j--){
            if (maze[i][j]!='#'){
                dp[2][i][j]=dp[2][i+1][j]+1;
                dp[3][i][j]=dp[3][i][j+1]+1;
            }
        }
    }
    for (int i=0;i<(int)vec.size();i++){
        int tx=vec[i].first,ty=vec[i].second;
        bool flag=false;
        for (int j=1;j<=q;j++){
            char ch=ins[j].s[0];
            int step=ins[j].x;
            if (ch=='N'){
                if (dp[0][tx][ty]>=step){
                    tx-=step;
                }
                else{
                    flag=true;
                    break;
                }
            }
            else if (ch=='S'){
                if (dp[2][tx][ty]>=step){
                    tx+=step;
                }
                else{
                    flag=true;
                    break;
                }
            }
            else if (ch=='E'){
                if (dp[3][tx][ty]>=step){
                    ty+=step;
                }
                else{
                    flag=true;
                    break;
                }
            }
            else{
                if (dp[1][tx][ty]>=step){
                    ty-=step;
                }
                else{
                    flag=true;
                    break;
                }
            }
        }
        if (!flag) v.push_back(maze[vec[i].first][vec[i].second]);
    }
    if ((int)v.size()==0) return puts("no solution")*0;
    sort(v.begin(),v.end());
    for (vector<char>::iterator it=v.begin();it!=v.end();it++){
        printf("%c",(*it));
    }
    puts("");
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注