louisfghbvc的部落格

題目大意: 給數字大小，起點與終點。問有幾條不重複的路徑。

思路: 暴搜，當然超時。觀察規律。 這題我沒想到，有請教AC的施大大。最後搞懂規律。

跟目標進行比較。每個位元都先跨出1步，接著開始從當前位元開始往低位走(走到底重新到最高位)，直到有1條路。邊走邊印。一定有m條不重複路徑。

代碼:  

#include <bits/stdc++.h>  
 
#define Fast cin.tie(0), ios::sync_with_stdio(0)  
using namespace std;  
  
int m, s, d;  
void dfs(int u, int i){  
    cout << " " << u;  
    if(u == d) return;  
    for(int k = 0, j = i-1; k < m; ++k, --j){  
        if(j < 0) j += m;  
        int v = u^(1<<j);  
        if((v&(1<<j)) != (d&(1<<j))) continue;  
        dfs(v, j);  
        break;  
    }  
}  
  
void solve(){  
    while(cin >> m >> s >> d){  
        for(int j = m-1; j >= 0; --j){  
            cout << s;  
            dfs(s^(1<<j), j);  
            cout << "\n";  
        }  
    }  
}  
  
int main()  
{  
    Fast;  
    solve();  
    return 0;  
}