CCF-CSP 201312-5 I'm stuck !

 I'm stuck

試題編号：	201312-5
試題名稱：	I’m stuck!
時間限制：	1.0s
記憶體限制：	256.0MB
問題描述：	問題描述 　　給定一個R行C列的地圖，地圖的每一個方格可能是'#', '+', '-', '|', '.', 'S', 'T'七個字元中的一個，分别表示如下意思： 　　'#': 任何時候玩家都不能移動到此方格； 　　'+': 當玩家到達這一方格後，下一步可以向上下左右四個方向相鄰的任意一個非'#'方格移動一格； 　　'-': 當玩家到達這一方格後，下一步可以向左右兩個方向相鄰的一個非'#'方格移動一格； 　　'|': 當玩家到達這一方格後，下一步可以向上下兩個方向相鄰的一個非'#'方格移動一格； 　　'.': 當玩家到達這一方格後，下一步隻能向下移動一格。如果下面相鄰的方格為'#'，則玩家不能再移動； 　　'S': 玩家的初始位置，地圖中隻會有一個初始位置。玩家到達這一方格後，下一步可以向上下左右四個方向相鄰的任意一個非'#'方格移動一格； 　　'T': 玩家的目标位置，地圖中隻會有一個目标位置。玩家到達這一方格後，可以選擇完成任務，也可以選擇不完成任務繼續移動。如果繼續移動下一步可以向上下左右四個方向相鄰的任意一個非'#'方格移動一格。 　　此外，玩家不能移動出地圖。 　　請找出滿足下面兩個性質的方格個數： 　　1. 玩家可以從初始位置移動到此方格； 　　2. 玩家不可以從此方格移動到目标位置。 輸入格式 　　輸入的第一行包括兩個整數R 和C，分别表示地圖的行和列數。(1 ≤ R, C ≤ 50)。 　　接下來的R行每行都包含C個字元。它們表示地圖的格子。地圖上恰好有一個'S'和一個'T'。 輸出格式 　　如果玩家在初始位置就已經不能到達終點了，就輸出“I'm stuck!”（不含雙引号）。否則的話，輸出滿足性質的方格的個數。 樣例輸入 5 5 --+-+ ..|#. ..|## S-+-T ####. 樣例輸出 2 樣例說明 　　如果把滿足性質的方格在地圖上用'X'标記出來的話，地圖如下所示： 　　--+-+ 　　..|#X 　　..|## 　　S-+-T 　　####X

問題連結：CCF201312試題。

問題描述：參見上文。

問題分析：這個問題可以用DFS（深度優先搜尋）來解決，需要兩次DFS。先從“S”點開始搜尋，找出其可以到達的點。這是如果從“S”點不可以到達“T”點，則輸出"I'm stuck!"，否則從“S”點可以到達點開始，逐個搜尋其可到達的點，統計那些不可到達“T”點的數量即可。

程式說明：（略）。

送出後得100分的C++語言程式如下：

/* CCF201312-5 I’m stuck! */

 

#include <iostream>

#include <cstring>

 

using namespace std;

 

const int N = 50;

const int DIRECTSIZE = 4;

struct _direct {

    int dr, dc;

} direct[DIRECTSIZE] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

 

char grid[N][N+1];

int visited[N][N], visited2[N][N];

 

int R, C;

 

// 判斷坐标是否合法或可移動到

inline bool islegal(int r, int c)

{

    if(0 <= r && r < R && 0 <= c && c < C && !visited[r][c] && grid[r][c] != '#')

        return true;

    else

        return false;

}

 

// 深度優先搜尋

void dfs(int r, int c)

{

    int nextr, nextc;

 

    visited[r][c] = 1;

 

    if(grid[r][c] == '+' || grid[r][c] == 'S' || grid[r][c] == 'T') {

        for(int i=0; i<DIRECTSIZE; i++) {

            nextr = r + direct[i].dr;

            nextc = c + direct[i].dc;

 

            if(islegal(nextr, nextc))

                dfs(nextr, nextc);

        }

    } else if(grid[r][c] == '-') {

        for(int i=2; i<DIRECTSIZE; i++) {

            nextr = r + direct[i].dr;

            nextc = c + direct[i].dc;

 

            if(islegal(nextr, nextc))

                dfs(nextr, nextc);

        }

    } else if(grid[r][c] == '|') {

        for(int i=0; i<2; i++) {

            nextr = r + direct[i].dr;

            nextc = c + direct[i].dc;

 

            if(islegal(nextr, nextc))

                dfs(nextr, nextc);

        }

    } else if(grid[r][c] == '.') {

        nextr = r + direct[1].dr;

        nextc = c + direct[1].dc;

 

        if(islegal(nextr, nextc))

            dfs(nextr, nextc);

    }

}

 

int main()

{

    int sr, sc, tr, tc;

 

    // 輸入資料

    cin >> R >> C;

    for(int i=0; i<R; i++)

        cin >> grid[i];

 

    // 找到起點和終點坐标

    for(int i=0; i<R; i++)

        for(int j=0; j<C; j++)

            if(grid[i][j] == 'S')

                sr = i, sc = j;

            else if(grid[i][j] == 'T')

                tr = i, tc = j;

 

    // bfs：标記從"S"點可以到達的點

    memset(visited, 0, sizeof(visited));

    dfs(sr, sc);

    memcpy(visited2, visited, sizeof(visited));

 

    if(visited2[tr][tc]) {

        int count = 0;

 

        // 統計"S"點可以到達、而不可到達"T"點的數量

        for(int i=0; i<R; i++)

            for(int j=0; j<C; j++) {

                if(visited2[i][j]) {    // "S"點可以到達的<i,j>點

                    // bfs：标記從<i,j>點開始可以到達的點，如果不能到達"T"點則計數

                    memset(visited, 0, sizeof(visited));

                    dfs(i, j);

 

                    if(!visited[tr][tc])

                        count++;

                }

            }

 

        // 輸出結果

        cout << count << endl;

    } else

        // 從"S"點不可以到達"T"點

        cout << "I'm stuck!" << endl;

 

    return 0;

}      

轉載于:https://www.cnblogs.com/hcw110/p/9410404.html