d907. 3. 城市走法計數
http://zerojudge.tw/ShowProblem?problemid=d907
在網路上做地圖查詢，例如查詢Google Map，可以知道某一點走到某一點的路徑，甚至於用滑鼠拖拉可以自行更改路徑。這些路徑，不管是系統建議的，或是自行拖拉更改的，都是走得通的。也就是說，電腦必須知道任意兩個地點，有哪些路徑走得通，才能做出自動建議，並允許使用者修改。
要達到這樣的功能，所需要的資料表達方式與考慮因素很多。在此，我們將問題簡化。假設有多個城市(或地點)，任意兩個城市之間只記錄有沒有路徑可通，那麼我們可以用圖形或矩陣來表達城市之間的路徑狀況，從中就可以推測並回答如下的問題：哪兩個城市沒有路徑可通？哪兩個城市必須剛好經過幾個城市才能走通，而且總共有幾種走法？
請參考下面的圖(如圖五)與矩陣(如圖六)，所顯示的路徑狀況。一般而言，n個城市之間的路徑狀況，在電腦中可以用一個矩陣M來表達。其中M的每一列由上而下分別代表城市1到城市n，其每一行由左至右，也代表城市1到城市n，因此矩陣M的「第i列第j行」的值若為「1」，則代表城市i到城市j有一條直達路徑，其值若為「0」，則代表城市i到城市j沒有直達路徑。
請根據上面的描述與範例，試寫程式，完成下列要求：
輸入說明 ：
第一列為城市個數，假設為n (1≤ n ≤ 10)。
第二列到第n+1列為上述矩陣的第1列到第n列，每一列由n個數字(0或1)表示，第i個數字表示該列中第i行的值，數字與數字中間沒有空格。
第n+2列為某一城市的編號，稱為i。
第n+3列為另一城市的編號，稱為j (i ¹ j)。
第n+4列為某一整數，稱為s (1≤ s ≤ 10)。 輸出說明 ：
請由螢幕輸出三列數字，說明如下：
第一列輸出從城市i，經過s個城市(可重複)後，到達城市j的不同走法個數。
第二列與第三列輸出不管經過幾個城市，都無法走通的其中一對城市，且此對城市的編號都是最小，而且第二列的值小於第三列的值；若沒有走不通的城市，則都輸出0。(詳見範例與說明) 範例輸入 ：
輸入範例一40110100010010010132輸入範例二40100100000000000121
範例輸出 ：
輸出範例一300輸出範例二013
提示 ：
出處 ：
/**********************************************************************************/
/* Problem: d907 "3. 城市走法計數" from 2010三重考區 */
/* Language: C */
/* Result: AC (4ms, 272KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-11 08:47:44 */
/**********************************************************************************/
#include<stdio.h>
#define Max 1000
typedef struct {
int t[10][10];
}Matrix;
Matrix A, In, init;
Matrix mult(Matrix x, Matrix y, int n) {
Matrix t = init;
int i, j, k;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
for(k = 0; k < n; k++) {
t.t[i][k] += x.t[i][j]*y.t[j][k];
}
return t;
}
int ans(int k, int i, int j, int n) {
Matrix x = In, y = A;
while(k) {
if(k&1) x = mult(x, y, n);
y = mult(y, y, n);
k /= 2;
}
return x.t[i-1][j-1];
}
int Floyd_Warshall(int n) {
int a, b, c;
for(a = 0; a < n; a++)
for(b = 0; b < n; b++)
if(A.t[a][b] == 0)
A.t[a][b] = Max;
for(a = 0; a < n; a++)
for(b = 0; b < n; b++)
for(c = 0; c < n; c++)
if(A.t[b][a] + A.t[a][c] < A.t[b][c])
A.t[b][c] = A.t[b][a] + A.t[a][c];
int tx = -1, ty = -1, flag = 1;
for(a = 0; a < n && flag == 1; a++)
for(b = 0; b < n && flag == 1; b++)
if(A.t[a][b] == Max) {
tx = a, ty = b;
flag = 0;
}
printf("%d\n%d\n", tx+1, ty+1);
}
main() {
int n, a, b, i, j, k;
char s[11];
while(scanf("%d", &n) == 1) {
for(a = 0; a < n; a++)
for(b = 0; b < n; b++)
A.t[a][b] = 0, In.t[a][b] = 0,
init.t[a][b] = 0;
for(a = 0; a < n; a++) In.t[a][a] = 1;
for(a = 0; a < n; a++) {
scanf("%s", s);
for(b = 0; b < n; b++)
A.t[a][b] = s[b] - '0';
}
scanf("%d %d %d", &i, &j, &k);
printf("%d\n", ans(k+1, i, j, n));
Floyd_Warshall(n);
}
return 0;
}