Koios1143的筆記

UVa 10500

發表於 分類於

UVa 10500

題目

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

給一張地圖，如果不能走的話會標記 $X$ ，你會從起點 $(x,y)$ 開始走，每次檢查4個方向，並將看到的結果記錄下來

檢查過程當中，依序檢查 北 東 南 西 ，第一次遇到可以走的就走過去

在4個方向都不能走的情況下結束，並輸出紀錄的結果以及走過的步數

想法

直接把走的過程模擬過一遍

從起點開始，每次檢查4個方向記錄下來，並且走向第一個可以走的地方

一直重覆到不能走為止，將結果輸出即可

記得方向要從 北->東->南->西

另外，在檢查四個方向的過程中，記得不要往走過的點走，不然可能會永遠不會結束喔w

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
using namespace std;
int n,m,x,y,dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
char arr[15][15], res[15][15];
bool vis[15][15];
void init(){
    // 初始化
    for(int i=0 ; i<15 ; i++){
        for(int j=0 ; j<15 ; j++){
            arr[i][j]='X';
            res[i][j]='?';
            vis[i][j]=false;
        }
    }
}
void print_table(){
    // 輸出表格的間隔
    for(int i=1 ; i<=m ; i++){
        cout<<"|---";
    }
    cout<<"|\n";
}
bool cango(int x, int y){
    // 判斷是否在圖的範圍內
    if(x<0 || x>n || y<0 || y>m) return false;
    return true;
}
int main(){
    while(cin>>n>>m && (n||m)){
        init();
        cin>>x>>y;
        for(int i=1 ; i<=n ; i++){
            for(int j=1 ; j<=m ; j++){
                cin>>arr[i][j];
            }
        }
        res[x][y]='0';
        vis[x][y]=true;
        int move=0;
        while(true){
            bool found=false;
            int found_x,found_y;
            for(int i=0 ; i<4 ; i++){
                int nx=x+dir[i][0];
                int ny=y+dir[i][1];
                res[nx][ny]=arr[nx][ny];
                if(cango(nx,ny) && arr[nx][ny]!='X' && !found && !vis[nx][ny]){
                    found=true;
                    found_x=nx;
                    found_y=ny;
                    vis[found_x][found_y]=true;
                }
            }
            if(found){
                x=found_x;
                y=found_y;
                move++;
            }
            else{
                break;
            }
        }
        cout<<"\n";
        for(int i=1 ; i<=n ; i++){
            print_table();
            for(int j=1 ; j<=m ; j++){
                if(j==1) cout<<"|";
                cout<<" "<<res[i][j]<<" |";
            }
            cout<<"\n";
        }
        print_table();
        cout<<"\n";
        cout<<"NUMBER OF MOVEMENTS: "<<move<<"\n"; 
    }

    return 0;
}

時間複雜度分析

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

每次針對4個方向尋找，時間複雜度視為 $O(1)$

最糟的情況需要將棋盤全部遍歷過，時間複雜度為 $O(nm)$

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

每筆測資總時間複雜度為 $O(3nm)$ 約為 $O(nm)$