Codeforces 106D Treasure Island 预处理前缀+暴力（水-白红宇

Codeforces 106D Treasure Island 预处理前缀+暴力（水

阅读量：7026 次

发布时间：2019-06-28

本文共 2246 字，大约阅读时间需要 7 分钟。

主题链接：

意甲冠军：

特定n*m矩阵

# 是墙 . 和字母是平地

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

以下k个指令。

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

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

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

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

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           using namespace std;#define N 1005vector
            
             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;}