本题需要去到矩阵里面进行dfs来求出所有的情况。当在矩阵里面走到边界的时候就是剪切结束的时候。那么剪切开始的时候就是在边界上。简单的来看就是从上下左右四个边上的点都走一遍且将走过的排除掉就是答案(定点当然不算)。这种简单粗暴地方式确实可以解,我也确实写了一遍。。。。。但是会超时。
我们垃圾代码:
#include <bits/stdc++.h> #include <unistd.h> using namespace std; const int maxn = 42; struct position{ int x; int y; }; int a, b; int ans = 0; int upper, down, left, right; map<pair<int, int>, bool> vis; map<pair<int, int>, bool> mp; int mv[4][2] = { {0,1}, {0,-1}, {1,0}, {-1,0} }; void dfs(int x, int y,int fax, int fay, int depth) { // cout<<x<<" "<<y<<endl; // if (mp[{x,y}]==1) return ; // mp[{x,y}] = 1; if (((x==0||x==a)||(y==0||y==b))&&(depth)&&(vis[make_pair(x, y)]==0)) { // cout<<"x="<<x<<" "<<"y="<<y<<endl; ans++; } if (((x==0||x==a)||(y==0||y==b))&&depth) { return ; } if(depth==0) { int next_x = x; int next_y = y; if (x==0) next_x++; if (x==a) next_x--; if (y==0) next_y++; if (y==b) next_y--; if ((next_x>a)||(next_x<0)||(next_y>b)||(next_y<0)||(next_x==fax&&next_y==fay)||(mp[{next_x,next_y}])) { // cout<<"进来了"<<endl; } else { mp[{next_x,next_y}] = 1; dfs(next_x, next_y, x, y, depth+1); mp[{next_x,next_y}] = 0; } } else for (int i=0;i<4;i++) { int next_x = x+mv[i][0]; int next_y = y+mv[i][1]; // cout<<"depth="<<depth<<endl; // cout<<"next_x="<<next_x<<" "<<"next_y="<<next_y<<endl; // sleep(1); if ((next_x>a)||(next_x<0)||(next_y>b)||(next_y<0)||(next_x==fax&&next_y==fay)||(mp[{next_x,next_y}])) { // cout<<"进来了"<<endl; continue; } if (((next_x==0||next_x==a)||(next_y==0||next_y==b))&&depth==0) { continue; } mp[{next_x,next_y}] = 1; dfs(next_x, next_y, x, y, depth+1); mp[{next_x,next_y}] = 0; } // mp[{x, y}] = 0; } int main() { cin>>a>>b; for (int i=0;i<=a;i++) { for (int j=0;j<=b;j++) { if (((i==0||i==a)||(j==0||j==b))&&(i!=0||j!=0)&&(!(i==0&&j==b))&&(!(i==a&&j==0))&&(!(i==a&&j==b))) { // cout<<"i="<<i<<" "<<"j="<<j<<endl; // sleep(1); dfs(i,j,0,0,0); // cout<<"ans="<<ans<<endl; vis[{i,j}] = 1; } } } cout<<ans; return 0; }但再去寻找规律的话,可以看到左右两边不同的在于剪切出来的在同一边。但左边的重复情况真好和右边的不同的对应。所以只需要遍历上边和左边两个边上的可以性且不去重即可。
还有就是可以在dfs开始的时候直接到边界开始的下一个点,这样方便dfs里面进行处理。我一开始图方便直接套的双重循环进行dfs。。。。及其麻烦还费事。。。。
#include <bits/stdc++.h> #include <unistd.h> using namespace std; const int maxn = 42; struct position{ int x; int y; }; int a, b; int ans = 0; int upper, down, left, right; map<pair<int, int>, bool> vis; map<pair<int, int>, bool> mp; int mv[4][2] = { {0,1}, {0,-1}, {1,0}, {-1,0} }; void dfs(int x, int y) { // cout<<x<<" "<<y<<endl; if (x==0||x==a||y==0||y==b) { // cout<<"x="<<x<<"y="<<y<<endl; ans++; return ; } mp[{x,y}] = 1; for (int i=0;i<4;i++) { int next_x = x+mv[i][0]; int next_y = y+mv[i][1]; if (mp[{next_x,next_y}]) { continue; } dfs(next_x, next_y); } mp[{x,y}] = 0; } int main() { cin>>a>>b; for (int i=1;i<a;i++) { // cout<<"a="<<i<<" b= "<<1<<endl; mp[{i,0}] = 1; dfs(i,1); mp[{i,0}] = 0; } for (int j=1;j<b;j++) { // cout<<"a="<<1<<" b= "<<j<<endl; mp[{0,j}] = 1; dfs(1,j); mp[{0,j}] = 0; } cout<<ans; return 0; }