C++ 基礎題 B – Red And Black HDU – 1312

好像還是 BFS

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

struct step{
    int x,y;
};

int main(){
    int n,m;
    while(cin>>m>>n){
        if(m==0) break;

        vector<string> mp;

        for(int i=0;i<n;i++){
            string s;
            cin>>s;
            mp.push_back(s);
        }

        deque<step> bfs;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(mp[i][j]=='@'){
                    step s;
                    s.y=i;s.x=j;
                    bfs.push_front(s);
                    mp[i][j]='#';
                }
            }
        }

        int ct=1;
        int dx[10]={0,1,0,-1},dy[10]={1,0,-1,0};
        while(!bfs.empty()){
            step now=bfs.back();
            bfs.pop_back();
            for(int i=0;i<4;i++){
                step next;
                next.y=now.y+dy[i];
                next.x=now.x+dx[i];
                if(next.y<0 || next.x<0 || next.y>=n || next.x>=m){
                    continue;
                }
                if(mp[next.y][next.x]=='.'){
                    mp[next.y][next.x]='#';
                    bfs.push_front(next);
                    ct++;
                }
            }
        }
        cout<<ct<<"\n";
    }
    return 0;
}

出處:https://vjudge.net/contest/240104#problem/B

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *