dfs暴力回溯,这个代码是我修改以后的,里面的go相当简洁,以前的暴力手打太麻烦,我也来点技术含量..
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define m 4 int caocao[4][2] = {0,0,0,1,1,0,1,1}; int go[3][3][2] = {{{0,1},{0,0}},{{1,0},{0,0}},{{0,0}}}; int kind[3] = {2,2,1}; int vis[6][6]; int n,tmp; void work_caocao(int x,int y) { int tmpx,tmpy; for(int i = 0; i < 4; i++) { tmpx = x + caocao[i][0]; tmpy = y + caocao[i][1]; vis[tmpx][tmpy] = 1; } } bool ok(int x,int y,int k) { for(int i = 0; i < kind[k]; i++) { int tmpx,tmpy; tmpx = x+go[k][i][0],tmpy = y+go[k][i][1]; if(vis[tmpx][tmpy]) return false; if(tmpx > n || tmpy > m) return false; if(tmpx <= 0|| tmpy <= 0) return false; } return true; } void set_vis(int x,int y,int k,int v) { for(int i = 0; i < kind[k]; i++) { int tmpx,tmpy; tmpx = x+go[k][i][0],tmpy = y+go[k][i][1]; vis[tmpx][tmpy] = v; } } void dfs(int x,int y) { if(y == m+1) { x++; y = 1; } if(x == n+1) { tmp++; return; } if(vis[x][y])dfs(x,y+1); for(int i = 0; i < 3; i++) { if(ok(x,y,i)) { //cout<<x << " "<<y<<endl; set_vis(x,y,i,1); dfs(x,y+1); set_vis(x,y,i,0); } } } void set_caocao(int x,int y) { for(int i = x; i < n; i++) for(int j = y; j < m; j++) { memset(vis,0,sizeof(vis)); //cout<<i<<" "<<j<<endl; work_caocao(i,j); dfs(1,1); } } int main() { int t; scanf("%d",&t); while(t--) { int ans[5]; ans[1] = 0,ans[2] = 18; for(int i = 3;i <= 4;i++) { n = i; tmp = 0; set_caocao(1,1); ans[i] = tmp; } int nn; scanf("%d",&nn); printf("%d ",ans[nn]); } }