{"id":498,"date":"2013-08-25T13:36:09","date_gmt":"2013-08-25T05:36:09","guid":{"rendered":"http:\/\/blog.dayandcarrot.net\/?p=498"},"modified":"2013-08-25T13:36:09","modified_gmt":"2013-08-25T05:36:09","slug":"zoj-problem-set-1002","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=498","title":{"rendered":"ZOJ Problem Set &#8211; 1002"},"content":{"rendered":"<p>\u539f\u9898\uff1a<a href=\"http:\/\/acm.zju.edu.cn\/onlinejudge\/showProblem.do?problemCode=1002\">http:\/\/acm.zju.edu.cn\/onlinejudge\/showProblem.do?problemCode=1002<\/a><br \/>\n\u8bd5\u6c34ZOJ\u7684\u7b2c\u4e00\u9898\uff0c\u679c\u7136ACM\u7684\u96be\u5ea6\u6bd4PAT\u5927\u4e00\u4e9b\uff0c\u5165\u95e8\u9898\u76ee\u90fd\u90a3\u4e48\u957f&#8230;<br \/>\n\u601d\u8def\u5176\u5b9e\u4e0d\u96be\uff0c\u5f04\u4e2a\u4e8c\u7ef4\u6570\u7ec4\u6765\u641e\uff0c\u6709\u70b9\u56de\u6eaf\u7684\u5473\u9053\uff0c\u521a\u5de7\u6700\u8fd1\u770b\u4e66\u770b\u5230\u4e86\u5206\u800c\u6cbb\u4e4b\u8fd8\u8981\u52a8\u6001\u89c4\u5212\u4ec0\u4e48\u7684<br \/>\n\u67d0\u4e00\u6b65\u7684\u7ed3\u679c= max{\u5f53\u524d\u4f4d\u7f6e\u653e\u7f6e1\u4e2a+\u540e\u9762\u4f4d\u7f6e\u653e\u7f6e\u4e2a\u6570, \u5f53\u524d\u4f4d\u7f6e\u653e\u7f6e0\u4e2a+\u540e\u9762\u4f4d\u7f6e\u653e\u7f6e\u4e2a\u6570}<br \/>\n\u7136\u540e\u5c31\u80fd\u505a\u5566~<br \/>\n&nbsp;<\/p>\n<pre>\n#include <iostream>\n#include <stdio.h>\n#include <string.h>\n#include <algorithm>    \/\/ std::max\nusing namespace std;\nenum state{\n    READY, BLOCK, DISABLED, USED\n};\n\/**\n\u4ecei,j \u5f00\u59cb\u627e\u4e0b\u4e00\u4e2a\u53ef\u7528\u7684\u4f4d\u7f6e\n**\/\nvoid findNextPossiblePos(int &i, int &j, int **inData, int N)\n{\n    for(int m=i; m<n; m++)\n    {\n        int n=0;\n        if(m == i)\n            n = j;\n        for(; n<n; n++)\n        {\n            if(inData[m][n] == READY)\n            {\n                i = m;\n                j = n;\n                return;\n            }\n        }\n    }\n    i = -1;\n    j = -1;\n    return;\n}\n\/**\n    \u8fd4\u56de\u503c\u4e3a\u6700\u5927\u7684\u6570\u91cf\n**\/\nint startJob(int** inData, int n, int i, int j)\n{\n    \/\/\u627e\u4e0b\u4e00\u4e2a\u53ef\u7528\u7684\u4f4d\u7f6e\n    findNextPossiblePos(i, j, inData, n);\n    if(i == -1)\n    {\n        \/\/\u518d\u4e5f\u627e\u4e0d\u5230\u4e86!\n        return 0;\n    }\n    \/\/if(mmax[i][j] != -1)\n    \/\/    return mmax[i][j];\n    \/\/else\n   int nextI = i;\n   int nextJ = j+1;\n   bool endFlag = false;\n   if(nextJ == n)\n   {\n       \/\/\u5230\u884c\u5c3e\u4e86\n       nextJ = 0;\n       nextI ++;\n       if(nextI == n)\n           endFlag = true; \/\/\u5230\u6700\u672b\u5c3e\u4e86\n   }\n    \/\/\u60c5\u51b51\uff0c\u5728\u672c\u53ef\u7528\u70b9\u653e\u7f6e\uff0c\u7136\u540e\u7ee7\u7eed\u5bfb\u627e\n    int **s1Data  = new int*[n];\n    for(int row=0; row<n; row++)\n        s1Data[row] = new int[n];\n    for(int r=0; r<n; r++)\n    {\n        for(int c=0; c<n; c++)\n            s1Data[r][c] = inData[r][c];\n    }\n    s1Data[i][j] = USED;\n    \/\/\u6807\u8bb0\u4e0d\u53ef\u7528\n    \/\/\u2191\n    for(int row = i-1; row>=0; row--)\n    {\n        if(s1Data[row][j] == BLOCK)\n            break;\n        s1Data[row][j]= DISABLED;\n    }\n    \/\/\u2193\n    for(int row = i+1; row<n; row++)\n    {\n        if(s1Data[row][j] == BLOCK)\n            break;\n        s1Data[row][j]= DISABLED;\n    }\n    \/\/\u2190\n    for(int col = j-1; col>=0; col--)\n    {\n        if(s1Data[i][col] == BLOCK)\n            break;\n        s1Data[i][col] = DISABLED;\n    }\n    \/\/\u2192\n    for(int col = j+1; col<n; col++)\n    {\n        if(s1Data[i][col] == BLOCK)\n            break;\n        s1Data[i][col] = DISABLED;\n    }\n    \/\/\n    int s1Result = 1 + startJob(s1Data, n, nextI, nextJ);\n    if(endFlag)\n    {\n    \/\/    mmax[i][j] = s1Result;\n        return s1Result;\n    }\n    \/\/\u60c5\u51b52\uff0c\u672c\u53ef\u7528\u70b9\u4e0d\u653e\u7f6e\n    int **s2Data  = new int*[n];\n    for(int row=0; row<n; row++)\n        s2Data[row] = new int[n];\n    for(int r=0; r<n; r++)\n    {\n        for(int c=0; c<n; c++)\n            s2Data[r][c] = inData[r][c];\n    }\n    int s2Result = startJob(s2Data, n, nextI, nextJ);\n    int retVal = (s1Result>s2Result)? s1Result:s2Result;\n    \/\/mmax[i][j] = retVal;\n    return retVal;\n}\nint main()\n{\n    int n;\n    while(cin >> n)\n    {\n        if(n == 0)\n            break;\n        \/\/create data\n        int **data = new int*[n];\n        for(int i=0; i<n; i++)\n        {\n            data[i] = new int[n];\n        }\n       \/\/ int **mmax = new int*[n];\n       \/\/ for(int i=0; i<n; i++)\n      \/\/  {\n      \/\/      mmax[i] = new int[n];\n     \/\/   }\n     \/\/   for(int i=0; i<n; i++)\n     \/\/   {\n    \/\/        for(int j=0; j<n; j++)\n    \/\/           mmax[i][j] = -1; \/\/\u6ca1\u6709\u8ba1\u7b97\u8fc7\n       \/\/ }\n        \/\/\/\/\/\/\/\/\/\/\/\/\n        \/\/Read data\n        for(int i=0; i<n; i++)\n        {\n            for(int j=0; j<n; j++)\n            {\n                char c;\n                cin >> c;\n                if(c == '.')\n                    data[i][j] = READY;\n                else if(c == 'X')\n                    data[i][j] = BLOCK;\n                else\n                    data[i][j] = DISABLED;\n            }\n        }\n        \/\/\/\/\/Start!\n        int result = startJob(data, n, 0, 0);\n        cout << result << endl;\n    }\n    return 0;\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u539f\u9898\uff1ahttp:\/\/acm.zju.edu.cn\/onlinejudge\/showProblem.do?problemCode=1002 \u8bd5\u6c34ZOJ\u7684\u7b2c\u4e00\u9898\uff0c\u679c\u7136ACM\u7684\u96be\u5ea6\u6bd4PAT\u5927\u4e00\u4e9b\uff0c\u5165\u95e8\u9898\u76ee\u90fd\u90a3\u4e48\u957f&#8230; \u601d\u8def\u5176\u5b9e\u4e0d\u96be\uff0c\u5f04\u4e2a\u4e8c\u7ef4\u6570\u7ec4\u6765\u641e\uff0c\u6709\u70b9\u56de\u6eaf\u7684\u5473\u9053\uff0c\u521a\u5de7\u6700\u8fd1\u770b\u4e66\u770b\u5230\u4e86\u5206\u800c\u6cbb\u4e4b\u8fd8\u8981\u52a8\u6001\u89c4\u5212\u4ec0\u4e48\u7684 \u67d0\u4e00\u6b65\u7684\u7ed3\u679c= max{\u5f53\u524d\u4f4d\u7f6e\u653e\u7f6e1\u4e2a+\u540e\u9762\u4f4d\u7f6e\u653e\u7f6e\u4e2a\u6570, \u5f53\u524d\u4f4d\u7f6e\u653e\u7f6e0\u4e2a+\u540e\u9762\u4f4d\u7f6e\u653e\u7f6e\u4e2a\u6570} \u7136\u540e\u5c31\u80fd\u505a\u5566~ &nbsp; #include #include #include #include \/\/ std::max using namespace std; enum state{ READY, BLOCK, DISABLED, USED }; \/** \u4ecei,j \u5f00\u59cb\u627e\u4e0b\u4e00\u4e2a\u53ef\u7528\u7684\u4f4d\u7f6e **\/ void findNextPossiblePos(int &#038;i, int &#038;j, int **inData, int N) { for(int m=i; m<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[138],"class_list":["post-498","post","type-post","status-publish","format-standard","hentry","category-study","tag-other-cpp"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/498","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=498"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/498\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=498"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=498"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=498"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}