题目链接：点击打开链接
题意：
给定n*m的矩阵
# 是墙 . 和字母是平地
最多有26个字母（不重复出现）
下面k个指令，
每个指令代表移动的方向和步数。
若以某个字母为起点，依次执行所有的指令，任何过程都不会撞到墙或走出地图，则这个字母合法。
按字典序输出所有合法的字母。若没有字母合法则输出' no solution'
预处理一下前缀和然后暴力。
#include #include #include #include #include #include #include using namespace std; #define N 1005 vector 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; }