{"id":194,"date":"2011-08-23T12:36:40","date_gmt":"2011-08-23T04:36:40","guid":{"rendered":"http:\/\/wangkaixuan.tech\/?p=194"},"modified":"2020-06-04T12:37:14","modified_gmt":"2020-06-04T04:37:14","slug":"poj-1154-letters","status":"publish","type":"post","link":"http:\/\/www.wangkaixuan.tech\/?p=194","title":{"rendered":"poj 1154 LETTERS"},"content":{"rendered":"\n
\/*\n\u8d70\u5b57\u6bcd\u201c\u8ff7\u5bab\u201d\n\u4ece\u5de6\u4e0a\u89d2\u7b2c\u4e00\u4e2a\u5b57\u6bcd\u5f00\u59cb\u904d\u5386\u56fe\n\u904d\u5386\u8fc7\u7684\u5b57\u6bcd\u4e0d\u518d\u904d\u5386\n\u95ee\u6700\u591a\u53ef\u4ee5\u904d\u5386\u591a\u5c11\u4e2a\u5b57\u6bcd\nDFS\u5e94\u7528\n\u4e0d\u96be\u7406\u89e3\n\u8be6\u89c1\u6ce8\u91ca\n\u4e00\u6b21AC\n*\/\n#define LOCAL\n#include<iostream>\n#include<cstdio>\n#include<cmath>\n#include<cstring>\n#include<cstdlib>\n#include<cctype>\n#include<iomanip>\n#include<string>\n#include<algorithm>\n#include<ctime>\n#include<stack>\n#include<queue>\n#include<vector>\n#define N 25\nusing namespace std;\nint map[N][N],mark[N][N],visit[30],ans,m,n,dir[4][2]={0,1,0,-1,1,0,-1,0};\n\/\/map\u8bb0\u5f55\u6574\u5f20\u56fe\u4e0a\u7684\u5b57\u6bcdmark\u8bb0\u5f55\u8bbf\u95ee\u8fc7\u7684\u7ed3\u70b9visit\u8bb0\u5f55\u6709\u54ea\u4e9b\u5b57\u6bcd\u5df2\u7ecf\u904d\u5386\u8fc7\u4e86\nbool legal(int x,int y)\/\/\u5224\u65ad\u5408\u6cd5\u6027\n{\n\tif(x>=1&&x<=m&&y>=1&&y<=n)\n\t\treturn true;\n\treturn false;\n}\nvoid DFS(int d,int x,int y)\/\/d\u4ee3\u8868\u641c\u7d22\u6df1\u5ea6\u540c\u65f6\u4e5f\u7b49\u4e8e\u5df2\u7ecf\u904d\u5386\u8fc7\u7684\u5b57\u6bcd\u4e2a\u6570\n{\n\tint i,sx,sy;\n\tfor(i=0;i<4;i++)\/\/\u5bf9\u5f53\u524d\u8282\u70b9[x,y]\u7684\u56db\u4e2a\u65b9\u5411\u8fdb\u884c\u63a2\u7d22\n\t{\n\t\tsx=x+dir[i][0];sy=y+dir[i][1];\n\t\tif(legal(sx,sy)&&(!visit[map[sx][sy]])&&(!mark[sx][sy]))\n\t\t\/\/\u5982\u679c\u5f53\u524d\u65b9\u5411\u662f\u5408\u6cd5\u7ed3\u70b9\u5e76\u4e14\u6ca1\u6709\u88ab\u8d70\u8fc7\u5e76\u4e14\u5f53\u524d\u8282\u70b9\u7684\u5b57\u6bcd\u6ca1\u6709\u88ab\u8bbf\u95ee\u8fc7\n\t\t{\/\/\u8bbf\u95ee\u4e4b\n\t\t\tmark[sx][sy]=1;\/\/\u6807\u8bb0\u5f53\u524d\u4f4d\u7f6e\u5df2\u88ab\u8bbf\u95ee\n\t\t\tvisit[map[sx][sy]]=1;\/\/\u6807\u8bb0\u5f53\u524d\u5b57\u6bcd\u5df2\u88ab\u8bbf\u95ee\n\t\t\tDFS(d+1,sx,sy);\/\/\u4ee5\u8be5\u8282\u70b9\u4e3a\u5f53\u524d\u8282\u70b9\u7ee7\u7eed\u63a2\u7d22\u4ed6\u7684\u56db\u4e2a\u65b9\u5411\n\t\t\tmark[sx][sy]=0;\/\/\u53cd\u6807\u8bb0\u8be5\u8282\u70b9\u4f4d\u7f6e\n\t\t\tvisit[map[sx][sy]]=0;\/\/\u53cd\u6807\u8bb0\u8be5\u5b57\u6bcd\n\t\t}\n\t}\n\tif(ans<d)\n\t\tans=d;\n}\nint main()\n{\n#ifdef LOCAL\n       freopen(\"input.txt\",\"r\",stdin);\n       freopen(\"output.txt\",\"w\",stdout);\n#endif\n \n\t   int i,j;char ch;\n\t   \/\/\u5f97\u5230\u56fe\n\t   while(cin>>m>>n)\n\t   {\n\t\t\tfor(i=1;i<=m;i++)\n\t\t\t{\n\t\t\t\tfor(j=1;j<=n;j++)\n\t\t\t\t{\n\t\t\t\t\tcin>>ch;\n\t\t\t\t\tmap[i][j]=ch-'A';\n\t\t\t\t}\n\t\t\t}\n\t\t\t\/\/\u521d\u59cb\u5316\n\t\t\tmemset(visit,0,sizeof(visit));\n\t\t\tmemset(mark,0,sizeof(mark));\n\t\t\tvisit[map[1][1]]=1;\/\/\u6807\u8bb0\u7b2c\u4e00\u4e2a\u88ab\u8bbf\u95ee\u7684\u4f4d\u7f6e\n\t\t\tmark[1][1]=1;\/\/\u6807\u8bb0\u7b2c\u4e00\u4e2a\u88ab\u8bbf\u95ee\u7684\u5b57\u6bcd\n\t\t\tans=0;\n\t\t\tDFS(1,1,1);\/\/\u4ece[1,1]\u5f00\u59cb\u8bbf\u95ee\u7b2c\u4e00\u4e2a\u5b57\u6bcd\n\t\t\tcout<<ans<<endl;\/\/\u8f93\u51fa\u7ed3\u679c\n\t   }\n\t\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[],"class_list":["post-194","post","type-post","status-publish","format-standard","hentry","category-06-01-acm"],"_links":{"self":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/194","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=194"}],"version-history":[{"count":0,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=\/wp\/v2\/posts\/194\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=194"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=194"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.wangkaixuan.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=194"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}