{"id":7,"date":"2022-06-04T10:52:00","date_gmt":"2022-06-04T02:52:00","guid":{"rendered":"http:\/\/ubuntu.tim-wcx.ltd\/wordpress\/index.php\/2022\/06\/04\/2021-02-24\/"},"modified":"2022-06-04T10:52:00","modified_gmt":"2022-06-04T02:52:00","slug":"2021-02-24","status":"publish","type":"post","link":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/2022\/06\/04\/2021-02-24\/","title":{"rendered":"2021-02-24"},"content":{"rendered":"<p><svg  style=\"display: none;\">\n                        <path stroke-linecap=\"round\" d=\"M5,0 0,2.5 5,5z\" id=\"raphael-marker-block\" style=\"-webkit-tap-highlight-color: rgba(0, 0, 0, 0);\"><\/path>\n                    <\/svg><\/p>\n<h2><a id=\"2020_icpc_asia_tehran_regional_contest_E_1\"><\/a>2020 icpc asia tehran regional contest E\u9898<\/h2>\n<h2><a id=\"Social_Distancing_2\"><\/a>Social Distancing<\/h2>\n<p><img decoding=\"async\" src=\"https:\/\/img-blog.csdnimg.cn\/20210224234306462.png?x-oss-process=image\/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjA0ODg0OA==,size_16,color_FFFFFF,t_70\" alt=\"\u5728\u8fd9\u91cc\u63d2\u5165\u56fe\u7247\u63cf\u8ff0\"><\/p>\n<h4><a id=\"_7\"><\/a>\u9898\u89e3<\/h4>\n<p><img decoding=\"async\" src=\"https:\/\/img-blog.csdnimg.cn\/img_convert\/26ca3e0c88a2227dc418772176bcafe5.png\" alt=\"img\"><\/p>\n<p><a href=\"https:\/\/blog.csdn.net\/weixin_37517391\/article\/details\/81807120\">\u5207\u6bd4\u96ea\u592b\u8ddd\u79bb\u548c\u66fc\u54c8\u987f\u8ddd\u79bb\u76f8\u4e92\u8f6c\u53d8<\/a><\/p>\n<p>\u6839\u636e\u4e0a\u8ff0\u6027\u8d28\uff0c\u53ef\u4ee5\u5c06\u6c42\u5207\u6bd4\u96ea\u592b\u4e0d\u7b49\u5f0f\u6700\u5c0f\u503c\u8f6c\u5316\u4e3a\u6c42\u66fc\u54c8\u987f\u8ddd\u79bb\u7684\u6700\u5c0f\u503c\u3002<\/p>\n<p>\u4e8c\u7ef4\u77e9\u9635\u6c42\u66fc\u54c8\u987f\u8ddd\u79bb\u53ef\u4ee5\u6839\u636e\u524d\u7f00\u548c\u6765\u51cf\u5c11\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u5982\u679c\u8be5\u70b9\u975e\u75c5\u4eba\uff0c\u6807\u8bb0\u4e3a1\uff0c\u4ee3\u8868\u8be5\u70b9\u6743\u503c\u4e3a1\uff1b\u53cd\u4e4b\u5219\u6807\u8bb0\u4e3a-1\uff0c\u540e\u671f\u6c42\u524d\u7f00\u548c\u65f6\u8be5\u70b9\u6743\u503c\u5b9a\u4e3a0\uff1b\u7136\u540e\u5206\u522b\u6cbf\u56db\u4e2a\u65b9\u5411\u6c42\u524d\u7f00\u548c\uff0c\u53d6\u6700\u5c0f\u503c\u5373\u4e3a\u6bcf\u4e2a\u70b9\u7684\u6700\u5c0f\u66fc\u54c8\u987f\u8ddd\u79bb\u3002<\/p>\n<p>\u6700\u540e\u6839\u636e\u6700\u5c0f\u66fc\u54c8\u987f\u8ddd\u79bbdfs\u8fdb\u884c\u641c\u7d22\u5373\u53ef\u5f97\u51fa\u7b54\u6848\u3002<\/p>\n<h4><a id=\"_19\"><\/a>\u4ee3\u7801<\/h4>\n<pre><code class=\"prism language-c++\">#pragma GCC optimize(2)\n#include <bits\/stdc++.h>\n#define inf 0x3f3f3f3f\nusing namespace std;\ntypedef long long ll;\nchar a[505][505]={0};\nint ans1[505][505]={0};\nint dis[505][505]={0};\nint sx,sy,ex,ey;\nstruct node\n{\n    int x,y,val;\n};\nint dx[]={0,1,-1,0,0};\nint dy[]={0,0,0,1,-1};\nint n,m;\nint ans=-1;\nint dfs(int x,int y,int val)\n{\n    if(ans>=val)\n        return 0;\n    if(x==ex&&y==ey)\n    {\n        ans=max(ans,val);\n        return 0;\n    }\n    for(int i=1;i<=4;i++)\n    {\n        int xx=x+dx[i],yy=y+dy[i];\n        if(xx<1||xx>n||yy<1||yy>m)\n            continue;\n        if(a[xx][yy]=='#')\n            continue;\n        int val1=min(val,dis[xx][yy]);\n        if(ans1[xx][yy]>=val1)\n            continue;\n        ans1[xx][yy]=val1;\n        dfs(xx,yy,val1);\n    }\n    return 0;\n}\nint mp[1050][1050]={0};\nint mp_sum1[1050][1050]={0};\nint mp_sum2[1050][1050]={0};\nint mp_sum3[1050][1050]={0};\nint mp_sum4[1050][1050]={0};\nint main()\n{\n    scanf(\"%d%d\",&n,&m);\n    for(int i=1;i<=n;i++)\n        scanf(\"%s\",a[i]+1);\n    for(int i=1;i<=n;i++)\n    {\n        for(int j=1;j<=m;j++)\n        {\n            dis[i][j]=inf;\n        }\n    }\n    for(int i=0;i<1050;i++)\n        for(int j=0;j<1050;j++)\n            mp_sum1[i][j]=mp_sum2[i][j]=mp_sum3[i][j]=mp_sum4[i][j]=inf;\n    int sum=0;\n    for(int i=0;i<=n+1;i++)\n    {\n        int j=0;\n        mp[i+j][i-j+500]=inf;\n        j=m+1;\n        mp[i+j][i-j+500]=inf;\n    }\n    for(int j=0;j<=m+1;j++)\n    {\n        int i=0;\n        mp[i+j][i-j+500]=inf;\n        i=n+1;\n        mp[i+j][i-j+500]=inf;\n    }\n    for(int i=1;i<=n;i++)\n    {\n        for(int j=1;j<=m;j++)\n        {\n            if(a[i][j]=='*')\n            {\n                sum++;\n                mp[i+j][i-j+500]=-1;\n            }\n            else\n            {\n                mp[i+j][i-j+500]=1;\n            }\n            if(a[i][j]=='S')\n                sx=i,sy=j;\n            if(a[i][j]=='E')\n                ex=i,ey=j;\n        }\n    }\n    for(int i=1;i<1050;i++)\n    {\n        for(int j=1;j<1050;j++)\n        {\n            if(mp[i][j]==-1)\n                mp_sum1[i][j]=0;\n            else\n                mp_sum1[i][j]=min(mp_sum1[i][j],min(mp_sum1[i-1][j],mp_sum1[i][j-1])+mp[i][j]);\n        }\n    }\n    \n    for(int i=1;i<1050;i++)\n    {\n        for(int j=1049;j>=1;j--)\n        {\n            if(mp[i][j]==-1)\n                mp_sum2[i][j]=0;\n            else\n                mp_sum2[i][j]=min(mp_sum2[i][j],min(mp_sum2[i-1][j],mp_sum2[i][j+1])+mp[i][j]);\n        }\n    }\n     \n     \n    for(int i=1049;i>=1;i--)\n    {\n        for(int j=1;j<1050;j++)\n        {\n            if(mp[i][j]==-1)\n                mp_sum3[i][j]=0;\n            else\n                mp_sum3[i][j]=min(mp_sum3[i][j],min(mp_sum3[i+1][j],mp_sum3[i][j-1])+mp[i][j]);\n        }\n    }    \n     \n \n    for(int i=1049;i>=1;i--)\n    {\n        for(int j=1049;j>=1;j--)\n        {\n            if(mp[i][j]==-1)\n                mp_sum4[i][j]=0;\n            else\n                mp_sum4[i][j]=min(mp_sum4[i][j],min(mp_sum4[i+1][j],mp_sum4[i][j+1])+mp[i][j]);\n        }\n    }\n \n    for(int i=1;i<=n;i++)\n    {\n        for(int j=1;j<=m;j++)\n        {\n            int xx=i+j,yy=i-j+500;\n            dis[i][j]=min(min(mp_sum1[xx][yy],mp_sum2[xx][yy]),min(mp_sum3[xx][yy],mp_sum4[xx][yy]));\n        }\n    }\n    \n    dfs(sx,sy,dis[sx][sy]);\n    if(ans!=-1&#038;&#038;sum==0)\n    {\n        printf(\"safen\");\n        return 0;\n    }\n    printf(\"%dn\",ans);\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>2020 icpc asia tehran reg&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-7","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/7","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/comments?post=7"}],"version-history":[{"count":0,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/posts\/7\/revisions"}],"wp:attachment":[{"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/media?parent=7"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/categories?post=7"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wordpress.tim-wcx.ltd\/index.php\/wp-json\/wp\/v2\/tags?post=7"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}