UVa 10189

題目

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

有一個地雷區，寬與長分別為 $n, m$ ，地雷以 * 表示

輸出每個非地雷的點四周八個方向總共有多少個地雷

想法

對於地圖上的每一個非地雷的點，直接檢查八個方向有多少地雷記錄下來即可

這裡有個小技巧，我們將八個方向 $x$ 和 $y$ 分別改變的大小用陣列記錄下來，接下來當我們要檢查八個方向，就只需要用 for 迴圈跑過一遍就可以了!

另外，這裡使用 cango 來判斷一個點是否超出範圍，在程式碼書寫上會變得更淺顯易懂

Code

#include<iostream>
using namespace std;
int n,m,Case=1,dir[8][2]={{1,0},{-1,0},{0,1},{0,-1},{-1,-1},{1,-1},{-1,1},{1,1}};
char arr[105][105];
bool cango(int x,int y){
    if(x<0 || x>=n || y<0 || y>=m) return false;
    return true;
}
int main(){
    bool out=false;
    while(cin>>n>>m && (n||m)){
        if(out){
            cout<<'\n';
        }
        else{
            out=true;
        }
        cout<<"Field #"<<Case++<<":\n";
        // input
        for(int i=0 ; i<n ; i++){
            for(int j=0 ; j<m ; j++){
                cin>>arr[i][j];
            }
        }
        // solve
        for(int i=0 ; i<n ; i++){
            for(int j=0 ; j<m ; j++){
                if(arr[i][j] == '*'){
                    cout<<'*';
                }
                else{
                    int cnt=0;
                    for(int k=0 ; k<8 ; k++){
                        // 枚舉八個方向 
                        int nx=i+dir[k][0];
                        int ny=j+dir[k][1];
                        // 點在範圍內 
                        if(cango(nx,ny)){
                            if(arr[nx][ny] == '*'){
                                cnt++;
                            }
                        }
                    }
                    cout<<cnt;
                }
            }
            cout<<'\n';
        }
    }
    return 0;
}

時間複雜度分析

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

最差情況對於每個點都要檢查八個方向，複雜度為 $O(8nm)$

單筆測茲的時間複雜度為 $O(9nm)$ 約為 $O(nm)$