ProblemJ Just the Last Digit (Floyd)

題目大意：

有一張有向圖，有一人遍地此路徑，於是她得出每個點有幾種不一樣的路徑，並繪製地圖
你的任務就是將此圖還原成原始地圖，如 a -> b , c -> b

分析：

對我而言這有點類似於 Floyd 演算法，但我沒有十足把握。有描繪出其大概想法，但卻沒辦法將演算法建立完成，需查看 Dup4’Blog 大神才有辦法解出。

由於題目有說明 i > j > k 所以不會有 5 > 3 > 2 問題加上路徑數量不會超過 10 (last digit 代表只會有 1 位數)，使問題簡單很多壓力將低，比起這年份的俄羅斯考卷只喜歡一值考時間優化好多了…。

我將我的程式想法說明，希望大家與未來的我可以看懂，嗚嗚嗚

array before = 題目給的
array after = 還原陣列

請先記住由於測試資料是 xxxxx 模式，所以透過 char 會來的比 int 陣列更方便輸入

下面的標題為 Line 行數
22. 由於路徑只會從小到大，於是從 i 開始遍地不斷嘗試
23. i -> j 的路徑收尋
24. sum = 紀錄過去的路徑
25. i -> k -> j 先假設玩家透過 i -> k ( Before 的路徑 )
26. after 要有才可以做 27. ，因為先前必須要有路徑才可以實行
27. 若是 after (必須要先確定有這個路徑，才可以用 sum 記錄才真實) 的路徑
30. 為甚麼是 sum +1? 例如說只有 2 個點 0 -> 1 ，在前面的程式 sum = 0，因為前面程式邏輯 after[i][k] 要有值 sum 才會增加紀錄，所以 +1 表示為單純只從 a -> b 次過程中並沒有其他的點。
31. 於是原始資料是有路徑的，所以透過 after 還原

對不起我解釋得很爛… 非常抱歉

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
char before[520][520] = {} ;
int after[520][520] = {} ;

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
#endif // LOCAL

    int n ;
    cin >> n ;
    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++)
            cin >> before[i][j] ;
    }

// 上面程式註解
    for(int i = 0 ; i < n ; i++){
        for(int j = i+1 ; j < n ; j++){
            int sum = 0 ;
            for(int k = i + 1 ; k < j ; k++){
                if(after[i][k])
                    sum += before[k][j]-'0' ;
            }

            if( (sum +1) % 10 == before[i][j] - '0'){
                after[i][j] = 1 ;
            }

        }
    }

    for(int i = 0 ; i < n ; i++){
        for(int j = 0; j < n ; j++)
            cout << after[i][j] ;
        cout << '\n' ;
    }

    return 0;
}