程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces 106D Treasure Island 預處理前綴和+暴力（水

Codeforces 106D Treasure Island 預處理前綴和+暴力（水

編輯：C++入門知識

Codeforces 106D Treasure Island 預處理前綴和+暴力（水

題目鏈接：點擊打開鏈接

題意：

給定n*m的矩陣

# 是牆 . 和字母是平地

最多有26個字母（不重復出現）

下面k個指令，

每個指令代表移動的方向和步數。

若以某個字母為起點，依次執行所有的指令，任何過程都不會撞到牆或走出地圖，則這個字母合法。

按字典序輸出所有合法的字母。若沒有字母合法則輸出' no solution'

預處理一下前綴和然後暴力。

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