主题链接：点击打开链接

意甲冠军：

特定n*m矩阵

# 是墙 . 和字母是平地

最多有26个字母（不反复出现）

以下k个指令。

每一个指令代表移动的方向和步数。

若以某个字母为起点，依次运行全部的指令，不论什么过程都不会撞到墙或走出地图。则这个字母合法。

按字典序输出全部合法的字母。若没有字母合法则输出' no solution'

预处理一下前缀和然后暴力。

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <string.h>

#include <math.h>

#include <vector>

#include <map>

using namespace std;

#define N 1005

vector<char>ans;

struct node{

    int x, y;

    char c;

    void put(){printf("(%d,%d) : %c\n", x, y, c);}

}a[30];

int step[4][2] = {-1,0, 1,0, 0,-1, 0,1};

int work[100005][2];

char s[N];

int mp[N][N], n, m, k, top, h[N][N], l[N][N];

bool okh(int H, int x, int y){return h[H][y]-h[H][x-1] == 0;}

bool okl(int L, int x, int y){return l[L][y]-l[L][x-1] == 0;}

bool ok(int x, int y, int i, int j){

    if(x>i)swap(x,i); if(y>j)swap(y,j);

    if(x==i)

        return okh(x, y, j);

    else

        return okl(y, x, i);

}

bool inmap(int x, int y){return 1<=x&&x<=n&&1<=y&&y<=m;}

bool judge(int x, int y){

    for(int i = 0; i < k; i++) {

        int ux = step[work[i][0]][0] * work[i][1] + x, uy = step[work[i][0]][1] *work[i][1] + y;

        if(!inmap(ux,uy))return false;

        if(!ok(x, y, ux, uy))return false;

        x = ux; y = uy;

    }

    return true;

}

void debug(){for(int i = 0; i < top; i++)a[i].put();}

void solve(){

 //   debug();

    ans.clear();

    for(int i = 0; i < top; i++)

        if(judge(a[i].x, a[i].y))

            ans.push_back(a[i].c);

    if(ans.size()==0){

        puts("no solution");

        return ;

    }

    sort(ans.begin(), ans.end());

    for(int i = 0; i < ans.size(); i++)printf("%c",ans[i]);

    puts("");

}

void input(){

    top = 0;

    memset(mp, 0, sizeof mp);

    memset(h, 0, sizeof h);

    memset(l, 0, sizeof l);

    for(int i = 1; i <= n; i++){

        scanf("%s", s+1);

        for(int j = 1; j <= m; j++)

        {

            if(s[j]=='#')

            {

                mp[i][j] = 1;

                h[i][j] = 1;

                l[j][i] = 1;

            }

            else if('A'<=s[j] && s[j]<='Z'){

                    a[top].x = i; a[top].y = j; a[top].c = s[j];

                    top++;

            }

        }

    }

    for(int i = 1; i <= n; i++)

        for(int j = 1; j <= m; j++)

            h[i][j] += h[i][j-1];

    for(int i = 1; i <= m; i++)

        for(int j = 1; j <= n; j++)

            l[i][j] += l[i][j-1];

    scanf("%d",&k);

    for(int i = 0; i < k; i++){

        scanf("%s %d", s, &work[i][1]);

        if(s[0] == 'N') work[i][0] = 0;

        else if(s[0]=='S') work[i][0] = 1;

        else if(s[0]=='W') work[i][0] = 2;

        else work[i][0] = 3;

    }

}

int main(){

    while(~scanf("%d %d",&n,&m)){

        input();

        solve();

    }

    return 0;

}