UVa 10010

題目

http://domen111.github.io/UVa-Easy-Viewer/?10010

給一個 $m \times n$ 的圖，每個格子上都有一個字

接下來會有 $k$ 個字串，要問這個字串在圖中的位置，並且保證一定存在

我們在圖中尋找的方向有8個 : 往左、往右、往上、往下、往左上、往左下、往右上、往右下

並且請忽視大小寫

想法

對於每個點，如果和詢問的第一個字相同，就以它為起點向8個方向找，如果找到答案就直接輸出

用 dir 陣列儲存八個方位的 $x, y$ 座標變化量

並且用 cango 判斷是否還在圖的範圍內

Code

#include<iostream>
using namespace std;
int t,m,n,k,dir[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
char arr[55][55];
string query;
bool out=false;
bool cango(int x,int y){
    // 判斷是否超出範圍
    if(x<0 || x>=m || y<0 || y>=n) return false;
    return true;
}
bool find_ans(int x, int y, int len){
    // 向8個方向找答案，並回傳是否找到答案
    for(int i=0 ; i<8 ; i++){
        bool end=true;
        for(int step=0 ; step<len ; step++){
            int nx=x+dir[i][0]*step;
            int ny=y+dir[i][1]*step;
            if(!cango(nx,ny) || arr[nx][ny]!=query[step]){
                // 不能走，或是不匹配則必定非為答案
                end=false;
                break;
            }
        }
        if(end) return true;
    }
    return false;
}
int main(){
    cin>>t;
    while(t--){
        if(out){
            cout<<"\n";
        }
        else{
            out=true;
        }
        cin>>m>>n;
        for(int i=0 ; i<m ; i++){
            for(int j=0 ; j<n ; j++){
                cin>>arr[i][j];
                arr[i][j]=tolower(arr[i][j]);
            }
        }
        cin>>k;
        while(k--){
            cin>>query;
            for(int i=0 ; i<query.size() ; i++){
                query[i]=tolower(query[i]);
            }
            bool end=false;
            int ans_x=-1,ans_y=-1;
            for(int i=0 ; i<m ; i++){
                for(int j=0 ; j<n && !end ; j++){
                    if(arr[i][j]==query[0] && find_ans(i,j,query.size())){
                        cout<<i+1<<" "<<j+1<<"\n";
                        end=true;
                    }
                }
            }
        }
    }
    return 0;
}

時間複雜度分析

輸入時間複雜度為 $O(mn)$

對於8個方位的查詢，時間複雜度可以估計為 $O(1)$

則查詢的時間複雜度約為 $O(mn)$

總時間複雜度為 $O(tmn)$