人材獲得作戦の問題を反復深化深さ優先探索で

人生を書き換える者すらいた。: 人材獲得作戦・４　試験問題ほか
反復深化深さ優先探索は、深さ優先探索の深さのリミットを少しずつ増やしながら行う探索で、幅優先探索に近い性質をもつ探索。

ゲーム木のように浅くて広い探索木の場合にメモリ効率が良く好まれる。

再帰で書けるので幅優先よりシンプル。

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

string maze;
vector<int> depths;
size_t w;
bool search(int x, int depth) {
    if(depth<=depths[x])return false;
    depths[x]=depth;
    if(maze[x]=='*')return false;
    if(maze[x]=='G')return true;
    if(
            search(x-w,depth-1)||
            search(x-1,depth-1)||
            search(x+1,depth-1)||
            search(x+w,depth-1)) {
        maze[x]='$';
        return true;
    }
    return false;
}

int main(int argc, char **argv)
{
    w = 0;
    vector<string> lines;
    while(!cin.eof()) {
        lines.push_back(string());
        getline(cin, lines.back());
        w = max(w, lines.back().size());
    }
    for(int i = 0; i < (int)lines.size(); i++) {
        lines[i].resize(w);
        maze.append(lines[i]);
    }
    int n = maze.size();
    int s = -1;
    depths.resize(n);
    for(int i = 0; i < n; i++) {
        if(maze[i]=='S')s=i;
    }
    for(int i = 0; !search(s,i); i++);
    maze[s]='S';
    for(int i = 0; i < (int)lines.size(); i++) {
        cout << string(maze, w*i, w) << endl;
    }
    return 0;
}

**************************
*S* *$$$$$               *
*$* *$ * $*************  *
*$*$$$*  $$************  *
*$$$ *    $$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$$$*$$$$$$$$$$$$$$G  *
*  *  $$$ *********** *  *
*    *        ******* *  *
*       *                *
**************************