{"id":90,"date":"2010-02-07T22:02:00","date_gmt":"2010-02-07T14:02:00","guid":{"rendered":"http:\/\/localhost\/?p=90"},"modified":"2010-02-07T22:02:00","modified_gmt":"2010-02-07T14:02:00","slug":"topcoder_srm_452_div_2_level_3_hamiltonpath","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=90","title":{"rendered":"TopCoder SRM 452 DIV 2 Level 3 HamiltonPath"},"content":{"rendered":"

\u7ed9\u5b9a\u4e00\u4e2a\u5b8c\u5168\u56fe\u548c\u4e00\u4e9b\u5fc5\u987b\u5305\u542b\u5728\u54c8\u5bc6\u987f\u8def\u4e2d\u7684\u8fb9\u3002\u3002\u6c42\u8fd9\u6837\u7684\u54c8\u5bc6\u987f\u8def\u6709\u51e0\u6761\u3002\u3002
\u5f88\u663e\u7136\u5982\u679c\u4e00\u4e2a\u70b9\u8fde\u63a5\u4e863\u6761\u6216\u4ee5\u4e0a\u7684\u5fc5\u987b\u8fb9\u7684\u8bdd\u3002\u3002\u5c31\u65e0\u89e3\u4e86\u3002\u3002\u6240\u4ee5\u5fc5\u987b\u8fb9\u4e00\u5b9a\u662f\u6210\u94fe\u51fa\u73b0\u7684\u3002\u3002
\u4e00\u4e2a\u67092\u4e2a\u6216\u4ee5\u4e0a\u8282\u70b9\u7ec4\u6210\u7684\u5fc5\u987b\u94fe\u6709\u4e00\u4e2a\u65b9\u5411\uff0c\u5c31\u662f\u56e0\u5b502
\u540c\u65f6\u5982\u679c\u6709n\u6761\u94fe\u7684\u8bdd\uff08\u5355\u4e2a\u8282\u70b9\u4e5f\u7b97\u94fe\u3002\u3002\uff09\u3002\u3002\u90a3\u4e48\u6392\u5217\u4e5f\u6709n\uff01\u7684\u56e0\u5b50\u3002\u3002
\u5168\u90e8\u4e58\u8d77\u6765\u5c31OK\u4e86\u3002\u3002
Code:
#include<string>
#include<vector>
#include<cstring>
using namespace std;
const int mod=1000000007;
class HamiltonPath
{
bool vis[50];
vector<string> map;
int num;
void dfs(int x)
{
vis[x]=true;num++;
for(int i=0;i<map.size();i++)
if(map[x][i]==’Y’&&!vis[i]) dfs(i);
}
public:
int countPaths(vector <string> m)
{
vector<int> d(m.size(),0);int cnt=0;map=m;long long ans=1;
for(int i=0;i<m.size();i++)
for(int j=0;j<m.size();j++)
{
if(m[i][j]==’Y’) d[i]++;
if(d[i]>2) return 0;
}
memset(vis,0,sizeof(vis));
for(int i=0;i<m.size();i++)if(!vis[i]){num=0;dfs(i);cnt++;if(num>1)ans*=2,ans%=mod;}
for(int i=1;i<=cnt;i++)ans*=i,ans%=mod;
return ans;
}
}; <\/p>\n","protected":false},"excerpt":{"rendered":"

\u7ed9\u5b9a\u4e00\u4e2a\u5b8c\u5168\u56fe\u548c\u4e00\u4e9b\u5fc5\u987b\u5305\u542b\u5728\u54c8\u5bc6\u987f\u8def\u4e2d\u7684\u8fb9\u3002\u3002\u6c42\u8fd9\u6837\u7684\u54c8\u5bc6\u987f\u8def\u6709\u51e0\u6761\u3002\u3002\u5f88\u663e\u7136\u5982\u679c\u4e00\u4e2a\u70b9\u8fde\u63a5\u4e863\u6761\u6216\u4ee5\u4e0a\u7684\u5fc5\u987b\u8fb9\u7684\u8bdd\u3002\u3002\u5c31\u65e0\u89e3\u4e86\u3002\u3002\u6240\u4ee5\u5fc5\u987b\u8fb9\u4e00\u5b9a\u662f\u6210\u94fe\u51fa\u73b0\u7684\u3002\u3002\u4e00\u4e2a\u67092\u4e2a\u6216\u4ee5\u4e0a\u8282\u70b9\u7ec4\u6210\u7684\u5fc5\u987b\u94fe\u6709\u4e00\u4e2a\u65b9\u5411\uff0c\u5c31\u662f\u56e0\u5b502\u540c\u65f6\u5982\u679c\u6709n\u6761\u94fe\u7684\u8bdd\uff08\u5355\u4e2a\u8282\u70b9\u4e5f\u7b97\u94fe\u3002\u3002\uff09\u3002\u3002\u90a3\u4e48\u6392\u5217\u4e5f\u6709n\uff01\u7684\u56e0\u5b50\u3002\u3002\u5168\u90e8\u4e58\u8d77\u6765\u5c31OK\u4e86\u3002\u3002Code:#include<string>#include<vector>#include<cstring>using namespace std;const int mod=1000000007;class HamiltonPath{ bool vis[50]; vector<string> map; int num; void dfs(int x) { vis[x]=true;num++; for(int i=0;i<map.size();i++) if(map[x][i]==’Y’&&!vis[i]) dfs(i); } public: int countPaths(vector <string> m) { vector<int> d(m.size(),0);int cnt=0;map=m;long long ans=1; for(int i=0;i<m.size();i++) for(int j=0;j<m.size();j++) { if(m[i][j]==’Y’) d[i]++; if(d[i]>2) return 0; } memset(vis,0,sizeof(vis)); for(int i=0;i<m.size();i++)if(!vis[i]){num=0;dfs(i);cnt++;if(num>1)ans*=2,ans%=mod;} for(int i=1;i<=cnt;i++)ans*=i,ans%=mod; return ans; }};<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/90"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=90"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/90\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=90"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=90"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=90"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}