読者です 読者をやめる 読者になる 読者になる

出来るだけ寝ていたい

1日最低12時間睡眠、寝たら負け

復習?bfs

今日は幅優先探索の勉強をしたよ。

今の今までdfsに重きを置いていたから、よくよく考えたらbfsの実装は今回が初めてだったかもしれない。

いつも通り蟻本の問題を解いた。前回のdfsの勉強と違ってかなりすんなり出来た。といっても3時間くらいかかったのかな。ミスがシンプルだったから良かった。

幅優先探索再帰的に実装するんじゃなくて、queueを使って次状態を保存していくやり方。
再帰的に実装しないからか関数の引数はvoidだった。(これについてはまだよくわかってないので断言出来ない。もっと経験を積みますね。)

あと余談だけど実装で初めて排他的論理和を使ったかもしれない。まあ、本当にどうでもいいのだけれど。

//poj
/*  .  ∧_∧
    ( ´・ω・)
    //\ ̄ ̄旦\
   // ※ \___\
   \\  ※  ※  ※ ヽ
     \ヽ-___--___ヽ*/

#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <sstream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <complex>
#include <vector>
#include <cstdio>
#include <cmath>
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define sort(v,n) sort(v,v+n);
#define vsort(v) sort(v.begin(),v.end());
#define vvsort(v) sort(v.begin(),v.end(),greater<int>());
#define ll long long
#define pb(a) push_back(a)
#define fi first
#define se second
#define inf 999999999
using namespace std;
typedef pair<int,int> P;
typedef pair<ll,ll> lP;
typedef priority_queue<int> PQ;
typedef priority_queue<int,vector<int>,greater<int> > RPQ;
bool is_uruu(int y) {
        return y % 4 == 0 && (y % 100 != 0 || y % 400 == 0);
}
template<class T>inline string toString(T x){
        ostringstream sout; sout<<x; return sout.str();
}
const ll MOD=1e9+7;
const double PI=acos(-1.0);
//-------------------------------------------------------------------------------------------------------------------------------------------//
int ny,mx;
char a[101][101];
int d[101][101];
int gx,gy;
int bfs(){
        for(int i=0; i<ny; i++) {
                for(int j=0; j<mx; j++) {
                        d[i][j]=inf;
                }
        }
        queue <P> q;
        for(int i=0; i<ny; i++) {
                for(int j=0; j<mx; j++) {
                        if(a[i][j]=='S') {
                                q.push(P(i,j));
                                d[i][j]=0;
                        }
                }
        }
        while(!q.empty()) {
                //cout<<"-------------------------------------------------"<<endl;
                int nowy=q.front().fi;
                int nowx=q.front().se;
                //cout<<nowy<<" "<<nowx<<endl;
                //cout<<d[nowy][nowx]<<endl;
                q.pop();
                if(a[nowy][nowx]=='G') {
                        gy=nowy;
                        gx=nowx;
                        break;
                }
                a[nowy][nowx]='#';
                for(int dy=-1; dy<=1; dy++) {
                        for(int dx=-1; dx<=1; dx++) {
                                if((dy^dx)!=0 && (dy^dx)!=-2 && (a[nowy+dy][nowx+dx]=='.'|| a[nowy+dy][nowx+dx]=='G') && d[nowy+dy][nowx+dx]==inf) {
                                        //cout<<"nowy+dy="<<nowy+dy<<" nowx+dx="<<nowx+dx<<endl;
                                        d[nowy+dy][nowx+dx]=d[nowy][nowx]+1;
                                        q.push(P(nowy+dy,nowx+dx));
                                }
                        }
                }
        }
        return d[gy][gx];
}

int main(){
        cin>>ny>>mx;
        for(int i=0; i<ny; i++) {
                for(int j=0; j<mx; j++) {
                        cin>>a[i][j];
                }
        }
        cout<<bfs()<<endl;
}

こんな感じ。
次からは貪欲法の勉強になります。