louisfghbvc的部落格

問題描述 ：

在象棋中馬的行走方法為棋盤中的”日”字，假設有一個N*M的棋盤，把一個馬放置在棋盤中的座標(H,K)，走過的路徑不能重複的限制下，請問馬從坐標(H,K)開始出發又跳回(H,K)有幾種方法。

輸入說明 ：

第一列有兩個正整數，分別用空格分開，第一列的兩正整數代表棋盤的大小N*M(水平線編號從0到N，垂直線編號從0到M)。第二列輸入有兩個正整數，分別用空格分開，表示馬放置在棋盤中的初始位置(H,K)。

棋盤左上角為(0,0);

輸出說明 ：

印出一個正整數代表馬從(H,K)出發共有幾種跳回(H,K)的方法。

思路: 

馬有八個方向走法,那麼從起點走8方向,紀錄是否拜訪過,如果走到原點就ans+1,邊界判斷不能超過棋盤大小,

這題頗怪的棋盤N*M那麼理論上來講3*3 只有9格吧但是這題來講是16格,然後xy座標也是算個坑點, N代表X軸, M是Y軸,

不過看題目的敘述感覺很像是水平線是y等於多少的線, 我以為N是走Y, 但我搞錯了, 總而言之就是如此。

程式碼:

#include <iostream>
#include <cstring>

using namespace std;
int n, m, h, k, sum;
bool vis[1005][1005];
int dir[][2] = { {1, 2}, {-1, 2}, {2, 1}, {-2, 1}, {1, -2}, {-1, -2}, {2, -1}, {-2, -1} };
void dfs(int x, int y){
    if(x == h && y == k && vis[x][y]){
        sum++;
        return;
    }
    for(int i = 0; i < 8; ++i){
        int a = x + dir[i][0];
        int b = y + dir[i][1];
        if(a >= 0 && a <= n && b >= 0 && b <= m && !vis[a][b]){
            vis[a][b] = true;
            dfs(a, b);
            vis[a][b] = false;
        }
    }
}
int main()
{
    while(cin >> n >> m >> h >> k){
        sum = 0;
        memset(vis, 0, sizeof vis);
        dfs(h, k);
        cout << sum << endl;
    }
    return 0;
}