【ABC備忘録】javaで解いたABCの問題のメモを置いていく

### D396(DFSの基本)
ABCのD396を例に、再帰によるDFSの基本についてまとめます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4112396/bc08ea34-74bb-47ad-996d-32ffb13fcda5.png)

単純パスとしてあり得るのは、最初が1、次に残りのN-1個から一つ選び...という操作を繰り返し、O((N-1)!)となり、N=10の場合にこれは10^6程度となり、全探索が可能になる。よってDFSによって全探索を行う。
```
  public static void dfs(int temp , long xor ,long label){
    xor = xor ^ label;
    visited[temp] = true;
    if (temp == N){
      visited[temp] = false;
      if (ans > xor){
        ans = xor;
      }
      return;
    }
    for (int i = 0 ; i < pointList[temp].size() ; i++){
      int next = pointList[temp].get(i);
      long nextLabel = labelList[temp].get(i);
      if (!visited[next]){
        dfs(next,xor,nextLabel);
      }
    }
    visited[temp] = false;
  }
  ```
  これがdfsの関数である。再帰によるdfsの特徴としては、自動で状態を保持してくれることがあげられる。
  最後のvisited[temp] = false;によって、一つのルートが限界までに行き切った時に、その点のvisitedをリセットしてから一つ上に戻ることができる。

### D398(逆の視点で動かすものを減らす)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4112396/dbfe6b84-d86e-45e8-84f0-9495ea6fe7c9.png)

愚直にやると、時刻tがあるので計算量がtとなり、それぞれの時刻についてtに比例する(最悪の場合が煙が被らなかった場合で、1,2,3...t と増えていくため)煙について操作を行う必要があり、全体でO(t^2)となり、計算量がオーバーする。

ここで、時刻tについてt回処理をすることは避けられないので、煙の操作側で計算量を減らしたい。ここで一度の操作で煙が全て同じ方法に動くことに注目すると、「煙以外を煙と逆方向に動かすことで、相対的に全ての煙を動かしたことにする」という解法を思いつく。(座標系を動かすイメージ)
以下がjavaによる実装例である。
```
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;

public class D398 {
  public static void main(String[]args)throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    HashSet<String> pointList = new HashSet<>();
    String[] firstLine = br.readLine().split(" ");
    int N = Integer.parseInt(firstLine[0]);
    int R = Integer.parseInt(firstLine[1]);
    int C = Integer.parseInt(firstLine[2]);
    String S = br.readLine();
    // 焚き火の座標
    int X = 0;
    int Y = 0;
    pointList.add(""+Y+ " "+X);
    for (Character c : S.toCharArray()){
      switch(c){
        case 'N':{
          R +=1;
          Y +=1;
          break;
        }
        case 'W':{
          C +=1;
          X +=1;
          break;
        }
        case 'S':{
          R -=1;
          Y -=1;
          break;
        }
        case 'E':{
          C -=1;
          X -=1;
          break;
        }
      }
      // 新しい煙をセット
      pointList.add(""+Y+ " " +X);
      // 高橋くんのところに煙があるかどうかの処理
      if (pointList.contains(""+R+ " " +C)){
        System.out.print(1);
      }else{
        System.out.print(0);
      }
    }
    
  }
}
```
座標が、(y,x)で与えられること、北側がマイナスであることに注意する。
```
    for (Character c : S.toCharArray()){
```
このようにして文字列をCharの配列にすることができる。(要素を一つずつ取り出して配列に挿入する必要があるが)
  
### D405(マップ型問題とBFSの基本)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4112396/60892b10-0a31-40c8-b3f4-8a59cba1bcec.png)

```
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class D405 {
  public static void main(String[]args)throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
    String [] firstLine = br.readLine().split(" ");
    int H = Integer.parseInt(firstLine[0]);
    int W = Integer.parseInt(firstLine[1]);
    Queue<int[]> queue = new LinkedList();
    // 地図の情報を格納。非常口マスは距離を0とし、それ以外は十分大きい数で定義する。(壁は-1)
    int [][] distMap = new int[H+1][W+1];
    // 解答となるマップ
    String [][] ansMap = new String[H][W];
    for (int i = 0 ; i < H ; i++){
      String[] line = br.readLine().split("");
      // 距離マップの作成
      for (int j = 0 ; j < W ; j++){
        if (line[j].equals("#")){
          distMap[i][j] = -1;
          ansMap[i][j] = "#";
        }else if (line[j].equals("E")){
          distMap[i][j] = 0;
          queue.add(new int[]{i,j});
          ansMap[i][j] = "E";
        }else if (line[j].equals(".")){
          distMap[i][j] = 2000000000;
        }
      }
    }
    while (!queue.isEmpty()){
      int[] point = queue.poll();
      int row = point[0];
      int col = point[1];
      if (row > H || col > W){
        continue;
      }else if (distMap[row][col] < 0){
        continue;
      }
      if (distMap[row+1][col] > 0){
        if (distMap[row+1][col] > distMap[row][col]+1){
          queue.add(new int[]{row+1,col});
          distMap[row+1][col] = distMap[row][col] +1;
          ansMap[row+1][col] = "^";
        }
      }
      if (row != 0){
        if (distMap[row-1][col] > 0){
          if (distMap[row-1][col] > distMap[row][col]+1){
            queue.add(new int[]{row-1,col});
            distMap[row-1][col] = distMap[row][col] +1;
            ansMap[row-1][col] = "v";
          }
        }
      }
      if (distMap[row][col+1] > 0){
        if (distMap[row][col+1] > distMap[row][col]+1){
          queue.add(new int[]{row,col+1});
          distMap[row][col+1] = distMap[row][col] +1;
          ansMap[row][col+1] = "<";
        }
      }
      if (col != 0){
        if (distMap[row][col-1] > 0){
          if (distMap[row][col-1] > distMap[row][col]+1){
            queue.add(new int[]{row,col-1});
            distMap[row][col-1] = distMap[row][col] +1;
            ansMap[row][col-1] = ">";
          }
        } 
      }
    }
    for (int i = 0 ; i < H ; i++){
      for (int j = 0 ; j < W ; j++){
        System.out.print(ansMap[i][j]);
      }
      System.out.println();
    }

  }
}
```
まずこれが全文である。
流れとして、答えを出力するマップを作成。(Eと#は入力読み込みの段階でこのマップに登録)
↓
Eからの距離マップを作成(Eと#は例外的な数値にしてのちの場合分けで使いやすいようにし、普通の通路(.)は最小を求めることを考えて、十分大きい数を代入しておく。

> 競プロにおける2次元座標は[row][col]であることに注意([x][y]じゃないよ)よって必然的にy軸にといて下側が+となる。
↓
BFSを行う
#### BFSの流れ
while (!isEmpty(queue))でループさせる
↓
複数スタート地点を全てqueueにaddする(今回なら全てのE)
↓
上下左右に行けるかどうか確認し、行ける(最短距離であるなら)なら次のマスをqueueに入れたのち、距離マップを現在地の距離マップを用いて更新
> ここで最短距離じゃない場合に、そもそもqueueに入れないことで、余計な試行を減らしている。


最終的に2重ループでansMapを出力して終了

> queueの操作は.add()と.poll()で行う