剪邮票
如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
#include <iostream> #include <cstdio> #include <cstdlib> #include <string> #include <cmath> #include <algorithm> #include <cstring> #include <map> #include <sstream> #include <queue> #include <stack> #define INF 0x3f3f3f3f #define mem(a,b) memset(a,b,sizeof(a)) #define For(a,b) for(int i = a;i<b;i++) #define ll long long #define MAX_N 100010 using namespace std; int ans,con; int mp[10][10],x[10],yes[20][20],vi[10][10]; bool vis[50]; int cur[4][2] = {-1,0,1,0,0,-1,0,1}; /* 其实对于solve函数我本来想这样来着：solve(int c,int r,int con); 但是这样用con作参数不知道怎么回事，最后的结果总是少。 所以就改成了全局的一个计数的变量。 */ void solve(int c,int r) { if(con == 5) { ans ++; return ; } for(int i = 0; i<4; i++) { int dx = c + cur[i][0]; int dy = r + cur[i][1]; if(dx<0 || dx>=3 || dy<0 || dy>=4) continue; if(yes[dx][dy] == 0 || vi[dx][dy] == 1) continue; vi[dx][dy] = 1; con ++; solve(dx,dy); } return ; } void dfs(int next) { if(next == 6) { mem(vi,0); int c,r; mem(yes,0); /* 以下注释部分和未注释部分是两种标记选取的方法。 */ // for(int i = 1; i<6; i++) // { // yes[x[i]] = 1; // } // int o = 0; // for(int i = 0; i<3; i++) // { // for(int j = 0; j<4; j++) // { // if(yes[mp[i][j]] == 1) // { // o = 1; // c = i; // r = j; // break; // } // } // if(o) break; // } int cut = 1; for(int i = 0; i<3; i++) { for(int j = 0; j<4; j++) { if(x[cut] == mp[i][j]) { c = i; r = j; yes[i][j] = 1; cut++; } if(cut == 6) break; } if(cut==6) break; } vi[c][r] = 1; con = 1; solve(c,r); return ; } for(int i = x[next - 1] + 1; i<=12; i++) { if(!vis[i]) { vis[i] = true; x[next] = i; dfs(next + 1); vis[i] = false; } } return ; } int main() { ans = 0; mem(vis,false); mem(x,0); int t = 1; for(int i = 0; i<3; i++) { for(int j = 0; j<4; j++) { mp[i][j] = t; t++; } } dfs(1); cout<<ans<<endl; return 0; }
