36時間くらい前まで「クラスって何、わけわかんない！」って言ってた僕が、AtCoderの深さ優先探索の迷路問題をPHPのクラスで解きました。ここに辿り着くまでにおよそ１日半かかりました。。これはもうダメだ、自分はプログラミング向いてないかも、放っておいて次の問題に行こうかなど考えました。
あとはプログラミングの動きをきちんと理解しておきたいので、ここでアウトプットします。
問題はこちら。
注意！こちらの記事は適宜追記していきます。m(._.)m
実装！
入力例
0行め：行の数 列の数
sスタート gゴール .通れる道 #壁
入力例2
10 10
s.........
######### .
# .......#.
# ..####.#.
## ....#.#.
##### .#.#.
g.#.#.#.#.
# .#.#.#.#.
# .#.#.#.#.
# .....#...
プログラム
Main.php
<?php
Class Maze {
//プロパティ。このクラスで使用するデータ。
private $h; //迷路の高さ。行（row）の数。
private $w; //迷路の幅。列（column）の数。
private $maze; //迷路の図面（mazeは英語で迷路）。
private $reached; //通った場所を記録していく配列。
private $goal; //ゴールしたかどうかの判定。
//コンストラクタ（上のプロパティは空なので、定義してあげる）
public function __construct($h, $w, $maze) { //$h,$w,$mazeはクラス外にあるので、それを引数経由で渡す。
$this->h = $h;
$this->w = $w;
$this->maze = $maze;
$this->reached[] = array(); //空の多次元配列を作っておいてあげる（多次元配列＝配列の中に配列がある状態）
}
//メソッド。迷路を探索する。
public function search($row, $col) { //探索するマスの行と列を引数で渡す
//迷路の外、もしくは壁（#）だったらreturn
if ($row < 0 || $this->h <= $row || $col < 0 || $this->w <= $col || $this->maze[$row][$col] == "#") {
return;
}
//もし既に通ったマスだったらreturn
if (isset($this->reached[$row][$col])) {
return;
}
//もしゴールだったら
if ($this->maze[$row][$col] == "g") {
//$this->goal = TRUE; //これ不要だったかも...
exit("Yes\n"); //ゴーール！
}
//通った箇所をreachedに記録しておく（mazeにではない）
$this->reached[$row][$col] = TRUE;
//隣のマスをチェックしにいく
self::search($row + 1, $col); //returnされるまでこの処理が続く
self::search($row - 1, $col);
self::search($row, $col + 1);
self::search($row, $col - 1);
return FALSE; //最後まで探索して"g"に辿り着けなかったらFALSEをreturn。
} //searchメソッド終了
} //クラス終了
//標準入力からデータ入手
//1行目を入手
fscanf(STDIN, "%d %d", $h, $w);
//迷路の図面とスタート地点を入手
for ($i = 0; $i < $h; $i++) {
fscanf(STDIN, "%s", $line); //まずは行ごと文字列として取得
$maze [] = str_split($line, 1); //1文字ずつ分割して配列へ格納
//一マスずつ取得しつつそれがスタート地点だったら保持しとく
if (strpos($line, "s") !== FALSE) { //strpos()は見つけられなかったらfalseを返します
$start = array($i, strpos($line, "s")); //何行目（$i）の何番目（strpos($line, "s")）か
}
}
$maze = new Maze($h, $w, $maze); //コンストラクタ（new Maze()）でオブジェクト$mazeを作る
$test = $maze->search($start[0], $start[1]);
if ($test == FALSE) { //もしfalseが帰ってきたらNoを出力
echo "No";
}
?>
- 迷路をどうやってプログラミングで表現するか？→多次元配列で保持できます。今回はそれを
$mazeという変数に持たせています。
まず、各マスを１つの値として保持しそれらを格納した配列を作ることで１行（row）を作ります。上の入力例でいくと0行目は["s", ".", ".", ".", ".", ".", ".", ".", ".", "."]となります。
次に、それら行をまた配列で保持してあげれば迷路を多次元配列で保持できます。配列群を配列で保持するということですね。
つまりスタート地点は、$maze[0][3]で表せます。 - うわ、出た
$this...→レシーバーというオブジェクトが入った変数。今の処理で作ろうとしているクラスのオブジェクトが入っている。
最後に
挫けそうになった時どうやって切り抜けたかメモ
将来また困難にブチ当たった時の自分のために。
- このコード実行されているかわからない。何回実行されているかわからない。→その前後に
echo "hello";とか書いておくとヒントになる。 - この変数なんだっけ？→とりま
var_dump();!!エラーが出るならexit;も便利。 - ずっと考えてもわからなかったら→席を立つ、違う作業をする、などして張り付かない！
Thanks to
プログラミングアカデミー、おさないさんのYouTube動画：PHPのクラスとオブジェクトについて解説します【PHPによるWebアプリケーション開発講座#17/クラスとオブジェクト】
Qiita記事：PHPで深さ優先探索を用いて迷路問題を解く
コメント大歓迎
です。