rustの深さ優先探索

深さ優先探索

AtCoder Beginner Contest 233のCが解けなくて解説見たら
DFSを使うと書いてあったので勉強してみた。幅優先探索と同じqiitaを参照した
https://qiita.com/drken/items/a803d4fc4a727e02f7ba

※追記　23/1/8　もうちょっと実装が分かりやすい奴を下のほうに入れたぞ

ここのグリッドグラフのところを実装してみた。
ちなみにこの問題はAtCoder Typical Contest A - 深さ優先探索　らしく
実装したのでコード提出してみたら83個中9個がWAだった。つまりいくつかのパターンではうまく動いていないらしい
なぜ・・・と思ったが一旦置いておく。
22/10/23 jh.jwをキャストするときにi8にしてたせいだった。i32にすることで無事AC
面倒なのはDFSの関数へ渡す引数が多いこと。
参照したqiitaもそうだが渡すのは次の探索箇所くらいでここでいうｃやseenは渡す必要ないが
rustではなかなか難しそうだったので渡す方針にした。
また、dfsの再帰のところでfor文の途中で再帰に入ってまた１からfor文回す・・・というイメージがなかなかわかず
書くのに苦労した。あとは範囲外の処理。この書き方だと負の値がただのでかい値になる。
つまり実はjh <0 || jw <0　はいらない。個人的には幅優先探索のほうが分かりやすくて良い。
使い分けはまだよくわかっていない

use proconio::{input};
use proconio::marker::{ Chars};
fn dfs(c:&Vec<Vec<char>> ,mut seen:&mut Vec<Vec<usize>>, vh:usize,vw:usize )  {
  seen[vh][vw] = 1;
  let d = vec![(-1, 0), (0, -1), (0, 1), (1, 0)];
  for (i,j) in &d{
    let jh = (vh as i32 + i) as usize;
    let jw = (vw as i32 + j) as usize;
    if jh <0 || jw <0 || jh >= seen.len() || jw >= seen[0].len(){continue}
    if c[jh][jw] == '#' as char {continue}
    if seen[jh][jw] == 1{continue}
    
    dfs(&c,&mut seen,jh,jw);
  }
}


fn main() {
  input!{
 H:usize,
  W:usize,
  c: [Chars;H]
  }
  let mut seen = vec![vec![0;W];H];
  let mut s = vec![0,0];
  let mut g = vec![0,0];
  for i in 0..H{
    for j in 0..W{
      if c[i][j] == 's' as char{
        s[0] = i;
        s[1] = j;
      }
      if c[i][j] == 'g' as char{
        g[0] = i;
        g[1] = j;
      }
    }
  }

  dfs(&c,&mut seen,s[0],s[1]);
  if seen[g[0]][g[1]] == 1{
    println!("{}","Yes");
  }else{
    println!("{}","No");
  }

}

ちょっと上はグリッドグラフの実装でわかりにくいのでグラフの実装も。
探索出来たら-1以外の値になるあとはこの実装だと到達するか否かしかわからないが
探索順番も求められるみたい

fn dfs(gra:&Vec<Vec<usize>>,v:usize,mut dist:&mut Vec<i32>,mut d:&mut usize){
   //探索順番を求めるときに使う（行きがけ）,このとき下の再帰関数の変数は`d*+1->dとすること
  //*d +=1;
  dist[v] = *d as i32;
  for i in &gra[v]{
    if dist[*i] != -1{
      continue;
    }
    dfs(gra,*i,&mut dist,&mut (*d+1));
  }
  //探索順番を求めるときに使う（帰りがけ）
  //*d +=1;
  //dist[v] = *d as i32;
}

fn main() {
 input! {
    n:usize,
    m:usize,
    v:[(usize,usize);m] 
  }

let mut gra = vec![vec![]; n];
let mut dist = vec![-1;n];
let mut d = 0;
//let mut queue =VecDeque::new();

  for (i,j) in v{
    gra[i-1].push(j-1);
    gra[j-1].push(i-1);
  }
  

dfs(&gra,0,&mut dist,&mut d);
println!("{:?}",&mut dist);

}