NKPATH - Đường đi trên lưới
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
#include <cstdio>
using namespace std;
int m, n, a[110][110], f[110][110], res;
int main() {
scanf("%d%d", &m, &n);
for(int i=0;i<m;++i) for(int j=0;j<n;++j) scanf("%d", &a[i][j]);
for(int i=0;i<m;++i) for(int j=0;j<n;++j) {
for(int u=0;u<=i;++u) for(int v=0;v<=j;++v) if(u+v<i+j && v<n-1) {
int x = a[i][j], y = a[u][v];
while(x!=0 && y!=0) {
if(x>y) x%=y; else y%=x;
}
if(x+y>1) f[i][j] = (f[i][j] + f[u][v]) % 1000000000;
}
if(j==0) f[i][j] = (1+f[i][j]) % 1000000000;
if(j==n-1) res = (res+f[i][j]) % 1000000000;
}
cout << res << endl;
//system("pause");
return 0;
}