C++ 基礎題 A – Lake Counting POJ – 2386

題目連結：宜中資訊校隊練習1 – DFS, BFS & Next_Permutation – Virtual Judge

這個問題主要在訓練 BFS ( 廣度優先搜索 )，以下為程式碼

#include<iostream>
#include<vector>
#include<string>
#include<deque>
using namespace std;

struct step{
    int x,y;
};

int main(){
    int n,m;
    vector<string> mp;
    bool used[110][110]={false};
    int dx[8]={-1,0,1,1,1,0,-1,-1},dy[8]={1,1,1,0,-1,-1,-1,0};

    cin>>n>>m;
    for(int i=0;i<n;i++){
        string s;
        cin>>s;
        mp.push_back(s);
    }
    deque<step> bfs;
    int pos=0;
    int ct=0;

    while(1){
        step stNow;stNow.x=0;stNow.y=0;
        if(!bfs.empty()){
            stNow=bfs.front();
            bfs.pop_front();

            if(stNow.y==n-1 && stNow.x==m-1){
                break;
            }
            for(int i=0;i<8;i++){
                step next;
                next.x=stNow.x+dx[i];
                next.y=stNow.y+dy[i];
                if(next.x>=0 && next.y>=0 && next.x<m && 
                   next.y<n && mp[next.y][next.x]=='W' && 
                   !used[next.y][next.x]){
                      used[next.y][next.x]=true;
                      bfs.push_back(next);
                }
            }
        }else{
            bool isFind=false;
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    if(mp[i][j]=='W' && used[i][j]==false){
                        used[i][j]==true;
                        step s;
                        s.y=i;s.x=j;
                        bfs.push_back(s);
                        isFind=true;
                        ct++;
                        break;
                    }
                }
                if(isFind) break;
            }
            if(!isFind){
                break;
            }
        }
    }
    cout<<ct;
    return 0;
}