剪邮票——两次DFS

本人水平有限&＃xff0c;仅供学习&＃xff0c;如有发现错误&＃xff0c;感谢指出

2016 —— T7

题目&＃xff1a;

思路&＃xff1a;
特判可以&＃xff0c;但容易漏情况&＃xff0c;这里考虑最朴素的方法&＃xff0c;不会漏掉。
1、先八个方向搜索&＃xff0c;再对八个方向搜出来的路径进行连通性判断&＃xff08;通过上下左右可以走到的DFS&＃xff09;

为什么要搜八个方向&＃xff1f;
因为dfs的时候需要回溯&＃xff0c;这样5和10对于6来说&＃xff0c;都是走一步可以达到的位置&＃xff0c;就不能同时存在了&＃xff0c;这样违反了上面的样例&＃xff0c;会漏掉情况。

2、判重&＃xff0c;对路径进行排序&＃xff0c;然后以字符串的形式存ID&＃xff0c;如把1 2 3 4 5 连接成串”12345”

对于搜索的路径因为 1 2 3 4 5&＃xff0c;和5 3 2 1 4其实是一条路径&＃xff0c;对于搜索的结果要判重。

tips&＃xff1a;由于在C&＃43;&＃43;中struct的实现是class&＃xff0c;这里没有typedef或加struct使用结构体&＃xff0c;文学爱好者谨慎观看&＃xff0c;码风诡异。

#include
using namespace std;int mp[5][5]&＃61;{{0,0,0,0,0},{0,1,2,3,4},{0,5,6,7,8},{0,9,10,11,12}};
int dx[8]&＃61;{1,-1,0,0,-1,-1,1,1},dy[8]&＃61;{0,0,-1,1,-1,1,-1,1},vis[5][5];
int xx[4]&＃61;{0,0,1,-1},yy[4]&＃61;{1,-1,0,0},book[5][5];
int cnt;
set<string>se;//judge repetitionstruct pos{int x,y;
};
pos path[20];string tostring(int n)
{stringstream ss;ss<<n;return ss.str();
}void dfs_check(pos p)
{book[p.x][p.y]&＃61;0;for(int i&＃61;0;i<4;i&＃43;&＃43;){pos t;t.x&＃61;p.x&＃43;xx[i],t.y&＃61;p.y&＃43;yy[i];if(book[t.x][t.y]&＃61;&＃61;0)continue;cnt&＃43;&＃43;;dfs_check(t);}return ;
}int check()
{cnt&＃61;1;memset(book,0,sizeof(book));for(int i&＃61;1;i<&＃61;5;i&＃43;&＃43;)book[path[i].x][path[i].y]&＃61;1;dfs_check(path[1]);return cnt&＃61;&＃61;5?1:0;
}void dfs(pos p,int step)//eight directions dfs
{if(step&＃61;&＃61;5){if(check()){string id&＃61;"";//生成唯一路径id利用set判重int temp[20];//将path路径复制一份&＃xff0c;避免排序后对原来回溯干扰for(int i&＃61;1;i<&＃61;5;i&＃43;&＃43;)temp[i]&＃61;mp[path[i].x][path[i].y];sort(temp&＃43;1,temp&＃43;6);for(int i&＃61;1;i<&＃61;5;i&＃43;&＃43;)id&＃43;&＃61;tostring(temp[i]);se.insert(id);}return ;}for(int i&＃61;0;i<8;i&＃43;&＃43;){pos t;t.x&＃61;p.x&＃43;dx[i],t.y&＃61;p.y&＃43;dy[i];if(t.x<1||t.x>3||t.y<1||t.y>4||vis[t.x][t.y]&＃61;&＃61;1)continue;vis[t.x][t.y]&＃61;1;path[step&＃43;1]&＃61;t;dfs(t,step&＃43;1);vis[t.x][t.y]&＃61;0;//recall}
}int main()
{for(int i&＃61;1;i<&＃61;3;i&＃43;&＃43;){for(int j&＃61;1;j<&＃61;4;j&＃43;&＃43;){memset(vis,0,sizeof(vis));pos s;s.x&＃61;i,s.y&＃61;j;//startpath[1]&＃61;s;vis[i][j]&＃61;1;dfs(s,1);}}return cout<<se.size()<<endl,0;
}