# b062. 1. 城市道路連通網
##### link: https://zerojudge.tw/ShowProblem?problemid=b062
###### tags: `Graph` `dp`

### 解法一：DFS( 最原始想法)
* 原本直接暴力DFS，會TLE。
* 需要記錄走過的狀態（當前城市 & 當前公里數）
* 下面程式碼中的 $record[cur][dis] = (cur==b)$ (14行) 意思是只要遞迴尋訪到目標城市( 不論當前公里數多少 )，則視為全新的一種走法，接著再由這個點往前推，看是否有其他解法，最後到達遞迴終點時在將路徑上的方法數加總，即為總方法數。

#include <bits/stdc++.h>
using namespace std;

int n;
int a, b, r;
int ans = 0;
string s;
set<vector<int>> st;

int dfs (int cur, int dis, vector<vector<int>>&table, vector<vector<int>> &record){
    if (dis>r) return 0; // 遞迴終點
    if (record[cur][dis]!=-1) return record[cur][dis]; 
    
    record[cur][dis] = (cur==b); 
    for (auto i:table[cur]){
        record[cur][dis]+=dfs(i,dis+1,table,record); // 每一個和 cur 節點有連通 的城市都跑一次，把方法數加起來
    }
    return record[cur][dis];
}

int main (){
  ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  while (cin >> n){
      cin.get ();
      vector < vector < int >>table (n); // 存圖，第 i 個城市和第 j 個城市連通

      for (int i = 0; i < n; i++){
	  getline (cin, s);
	  for (int j = 0; j < n; j++){
	      if (s[j] == '1'){
		  table[i].push_back (j);
		    }
	    }
	}
      cin >> a >> b >> r;
      vector<vector<int>> record(n,vector<int>(r+1,-1)); // 陣列儲存的內容是該城市在某個公里數所有的走法數
      a--;
      b--;
      
      cout << dfs (a, 0, table, record)<< "\n";
    }

  return 0;
}

### 解法二：DP

* 建立一個 $DP[x][y]$，$x$ 代表城市，$y$ 代表走的公里數
* 窮舉每一個走的公里數 $y$ ( 1~最大公里數 )，每次都針對每一個城市進行計算，當兩個城市相連時( 如 $a$, $b$ 兩個城市)： <font color="ff123">$DP[a][y]+=DP[b][y-1]$</font>
* 最後輸出 $\sum_{k=1}^{N}DP[j][k]$ => $j$ 代表目標城市

#include <bits/stdc++.h>

using namespace std;

int n;
int a, b, r;
int ans = 0;
string s;

int main (){
      ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
      while (cin >> n){
          cin.get ();
          vector < vector < int >>table (n);
            ans=0;
          for (int i = 0; i < n; i++){
          getline (cin, s);
          for (int j = 0; j < n; j++){
              if (s[j] == '1'){
              table[i].push_back (j);
                }
            }
        }
          cin >> a >> b >> r;
          vector<vector<int>> dp(n,vector<int>(r+1,0));

          a--;
          b--;
          dp[a][0]=1;
          for (int i=1;i<=r;i++){
              for (int j=0;j<n;j++){
                  for (auto k:table[j]){
                      dp[j][i]=dp[j][i]+dp[k][i-1];
                  }
              }
          }

          for (int i=1;i<=r;i++){
              ans+=dp[b][i];
          }
          cout<<ans<<"\n";
        }

      return 0;
}