剪枝：这里只是用到了一个小剪枝对于a[x],b[y] 都要判断一下是不是已经等于0了
还有对于dfs和bfs 我们一定要分清哪一个是x轴哪一个是y轴（竖着的是x，横着的是y），我们一定要处理要输入输出，否则存的图就是不一样的，这样就大意失荆州，见祖宗了。
这里用到vector数组进行路径的记录；
#include<iostream> #include<algorithm> #include<cstring> #include<vector> using namespace std ; const int N = 50 ; int a[N] , b[N] ; int n ; bool v[N][N] ; int d[4][2] = {{0,1},{0,-1},{1,0},{-1,0}} ; vector<pair<int,int>> q ; void dfs(int x, int y){ //if(a[x] < 0 || b[y] < 0) return; if(x==n-1 && y==n-1){ bool flag = 1 ; for(int i = 0; i < n ; i ++) if(a[i]) flag = 0 ; for(int i = 0 ; i < n ; i ++) if(b[i]) flag = 0 ; if(flag){ for(int i = 0 ; i < q.size() ; i ++){ cout << q[i].first * n + q[i].second <<" " ; } } } for(int i = 0 ; i < 4 ; i ++){ int tx = x + d[i][0] , ty = y + d[i][1] ; if(tx < 0|| tx>=n || ty < 0 || ty >= n) continue ; if(v[tx][ty]) continue ; a[tx] -- ; b[ty] -- ; v[tx][ty] = 1 ; q.push_back({tx,ty}) ; dfs(tx,ty) ; a[tx] ++ ; b[ty] ++ ; v[tx][ty] = 0 ; q.pop_back() ; } } int main(){ cin >> n ; for(int i = 0 ; i < n ; i++) cin >> b[i] ; for(int i = 0 ; i < n ; i++) cin >> a[i] ; v[0][0] = 1 ; a[0] -- ,b[0] -- ; q.push_back({0,0}) ; dfs(0,0) ; }
