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

出来るだけ寝ていたい

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

復習dfs ver2

前回同様、深さ優先探索の復習をしていました。今回も予想だにしなかったところでWAを招いてしまいました。2日でdfsの知識不足となる点が二箇所も分かったから嬉しい限りですがね。
今回解いていた問題はPKUのlake countingという問題。簡潔に言うと池の数数えてねっていう問題です。
最初は方針で悩んで、悩み続けて、方針を解説読んで把握しました。
んで、実装。
何も見ずに出来ると思ってやった。やれた。試しにテストケースに当てはめる。
あれれ、、違う。。
なんでだ??と思いデバッグ
違ってるところは分かった。けど、どう直す??
しばらく考えて思いついたのが、「あ!もしかして深さ優先探索は探索していく方向も考えなきゃいけないのか?!8方向を適当な順で書いたらいけないのかな!」と思い方向の順を考え始める。
(しかし、全ては僕がこんな罠にかかってしまった事が原因だった…)
何も知らずに僕は探索する方向を変えて実行。
奇跡的にテストケースの1つが通った。
あー、やっぱりそうだったかー。なんて考えた僕は愚かだった。そして無知だった。
よーし、PKUのオンラインジャッジに提出するぞー!と意気込み提出。

結果は WA

何故??え、なんでだ??これが答えじゃないの?もしかして問題違う??などと戸惑う俺。
試しに自分で作ったテストケースを入力する。
すると全く違う答えが出力された。
まだ、何か違うらしい。
そしてまたまた方向の順番を考える俺。
試しに解説の順番と同じにして実行。
答えは違った。。
今まで順番を気にしてきた俺だが、どうやらそれは関係ないらしい。。
じゃあ一体何が違うんだ。。

ここで、仕方がないから試しに解説のコードを丸写ししてみる。
実行する。テストケース通る。PKUに提出。

結果は AC

えー??一体自分のさっきまでのコードとこれ、何が違うの??ほとんど同じじゃん。真面目にわからないんだけど。。
見比べてみる。
すると、1つの違いが見えた。
解説はif文の中にdfs()が書いてある。
僕のはif文の中にreturn dfs()と書いてある。

まぁ、起こることは同じだろうけど。。と思いながらreturnを除いて実行。
テストケースが通る。
???????!!、!、!!!!!
え、これが違ったの??え、俺returnで苦しめられてたの??
更に、returnってなんだ??ということにも。
体に染み付いたggrks精神がうごめき、即wikipedia
数値を呼び出すと共に関数を終了させるもの。と書いてある。知ってた。知ってるつもりだった。関数を呼び出す時にも関数を終了させるとは思ってなかった。。return dfs()なんてやったら、そもそも深さ優先探索じゃない。。ただの再帰でしかない。。それを瞬間的に理解した。
そして、深さ優先探索を実装する時はreturn dfs()なんて死んでもやらないんだとも理解した。長かった。。理解までが本当に長かった。これだから独学は辛い。でも、一番勉強になる。
深さ優先探索を完全に理解できた。

//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);
//-------------------------------------------------------------------------------------------------------------------------------------------//
char a[101][101];
int ny,mx;//x->m,y->n
int ans;
void dfs(int nowy,int nowx){
        a[nowy][nowx]='.';
        //cout<<nowy<<" "<<nowx<<endl;
        /*for(int dx=-1; dx<=1; dx++) {
                for(int dy=-1; dy<=1; dy++) {
                        int nowyy=nowy+dy;
                        int nowxx=nowx+dx;
                        if(nowyy>=0 && nowyy<ny && nowxx>=0 && nowxx<mx && a[nowyy][nowxx]=='W') dfs(nowyy,nowxx);
                }
           }*/
        if(nowx>0 && nowy>0 && a[nowy-1][nowx-1]=='W') {
                dfs(nowy-1,nowx-1);
        }
        if(nowx>0 && a[nowy][nowx-1]=='W') {
                dfs(nowy,nowx-1);
        }
        if(nowx>0 && nowy<ny-1 && a[nowy+1][nowx-1]=='W') {
                dfs(nowy+1,nowx-1);
        }
        if(nowy>0 && a[nowy-1][nowx]=='W') {
                dfs(nowy-1,nowx);
        }
        if(nowy<ny-1 && a[nowy+1][nowx]=='W') {
                dfs(nowy+1,nowx);
        }
        if(nowx<mx-1 && nowy>0 && a[nowy-1][nowx+1]=='W') {
                dfs(nowy-1,nowx+1);
        }
        if(nowx<mx-1 && a[nowy][nowx+1]=='W') {
                dfs(nowy,nowx+1);
        }
        if(nowx<mx-1 && nowy<ny-1 && a[nowy+1][nowx+1]=='W') {
                dfs(nowy+1,nowx+1);
        }
        return;
}



int main(){
        cin>>ny>>mx;
        for(int i=0; i<ny; i++) {
                for(int j=0; j<mx; j++) {
                        cin>>a[i][j];
                }
        }
        //cout<<"------------------------------------------------------"<<endl;
        ans=0;
        for(int i=0; i<ny; i++) {
                for(int j=0; j<mx; j++) {
                        if(a[i][j]=='W') {
                                dfs(i,j);
                                /*for(int k=0; k<ny; k++) {
                                        for(int l=0; l<mx; l++) {
                                                cout<<a[k][l];
                                                if(l==mx-1) cout<<endl;
                                        }
                                   }
                                   cout<<"------------------------------------------------------"<<endl;*/
                                ans++;
                        }
                }
        }
        cout<<ans<<endl;
        return 0;
}

これが今日書いたコード。これに9時間費やしただよ僕は。明日からは幅優先探索をやろうと思う。