{"id":2244,"date":"2009-10-14T15:46:43","date_gmt":"2009-10-14T15:46:43","guid":{"rendered":"http:\/\/192.168.0.71:9090\/?p=1946"},"modified":"2009-10-14T15:46:43","modified_gmt":"2009-10-14T15:46:43","slug":"programming-challenges-%ec%9e%91%ec%9d%80-%eb%b9%84%ec%88%8dlittle-bishops","status":"publish","type":"post","link":"https:\/\/talsu.net\/?p=2244","title":{"rendered":"Programming Challenges &#8211; \uc791\uc740 \ube44\uc20d(Little Bishops)"},"content":{"rendered":"<p><span style=\"font-size: 12pt; font-weight: bold;\"><a title=\"[http:\/\/programming-challenges.com\/pg.php?page=downloadproblem&amp;probid=110801&amp;format=html]\ub85c \uc774\ub3d9\ud569\ub2c8\ub2e4.\" target=\"_blank\" href=\"http:\/\/programming-challenges.com\/pg.php?page=downloadproblem&amp;probid= 110801&amp;format=html\">\ubb38\uc81c &lt;- \ud074\ub9ad<\/a><\/span><\/p>\n<p>\uc774\ub7f0 \uc2a4\ud0c0\uc77c\uc758 \ubb38\uc81c\uc5d0 \uc57d\ud558\ub2e4 \uc0dd\uac01 \ud588\ub294\ub370 \uc5ed\uc2dc \ud798\ub4e4\ub2e4..  \ud480\uae34 \ud588\uc73c\ub098 \uc2dc\uac04 \uc81c\ud55c\uc5d0 \uc790\uafb8 \uac78\ub9b0\ub2e4 \uadf8\uac83\ub3c4 \ud131\uc5c6\uc774..<\/p>\n<p>\uc2dc\ud5d8 \uba87\uc77c \ub0a8\uc9c0\ub3c4 \uc54a\uc558\ub294\ub370 \uc660\uc9c0 \uc774\ub7f0 \uc2a4\ud0c0\uc77c\uc758 \ubb38\uc81c\uac00 \ub098\uc62c\uaebc \uac19\uc544 \ubd88\uc548 \ud558\ub2e4..<br \/>\n<br \/>\uc5b4\uca0b\ub4e0 \uc544\uc9c1 \ubbf8\uc644..<\/p>\n<pre class=\"lang:c++ decode:true\">\n#include <iostream>\n#include <vector>\n#include <deque>\n\/\/class FieldOld{\n\/\/\ttypedef std::pair<int, int> POS;\n\/\/\tstd::vector<pos> stack;\n\/\/\tint fieldSize;\n\/\/public:\n\/\/\tFieldOld(int size):fieldSize(size){}\n\/\/\n\/\/\tint get(int x, int y){\n\/\/\t\tif(x<0 || x > (fieldSize-1) || y < 0 || y > (fieldSize - 1))\n\/\/\t\t\treturn -1;\n\/\/\t\tPOS pos(x,y);\n\/\/\t\tstd::vector<pos>::iterator it;\n\/\/\t\tfor(it = stack.begin(); it!= stack.end(); ++it){\n\/\/\t\t\tif((*it) == pos)\n\/\/\t\t\t\treturn 1;\n\/\/\t\t}\n\/\/\t\treturn 0;\n\/\/\t}\n\/\/\tvoid push(int x, int y){\n\/\/\t\tPOS pos(x,y);\n\/\/\t\tstack.push_back(pos);\n\/\/\t}\n\/\/\tvoid pop(){\n\/\/\t\tif(!stack.empty())\n\/\/\t\t\tstack.pop_back();\n\/\/\t}\n\/\/\n\/\/\tint size(){\n\/\/\t\treturn fieldSize;\n\/\/\t}\n\/\/\n\/\/\tint stackSize(){\n\/\/\t\treturn stack.size();\n\/\/\t}\n\/\/\n\/\/\n\/\/};\n\nclass Field{\n\ttypedef std::pair<int, int> POS;\n\tstd::deque<pos> stack;\n\n\t\/\/std::vector< std::vector<int> > field;\n\tchar field[8][8];\n\tint fieldSize;\npublic:\n\tField(int size):fieldSize(size){\n\t\t\/\/field.resize(size);\n\t\t\/\/std::vector< std::vector<int> >::iterator it;\n\t\t\/\/for(it = field.begin(); it!=field.end(); ++it){\n\t\t\/\/\tit->resize(size);\n\t\t\/\/\tstd::vector<int>::iterator iit;\n\t\t\/\/\tfor(iit = it->begin(); iit!= it->end(); ++iit){\n\t\t\/\/\t\t*iit = 0;\n\t\t\/\/\t}\n\t\t\/\/}\n\t\tfor(int i = 0 ; i < 8; ++i){\n\t\t\tfor(int j = 0; j < 8; ++j){\n\t\t\t\tfield[i][j] = 0;\n\t\t\t}\n\t\t}\n\n\t}\n\n\tint get(int x, int y){\n\t\tif(x<0 || x > (fieldSize-1) || y < 0 || y > (fieldSize - 1))\n\t\t\treturn -1;\n\t\t\/\/POS pos(x,y);\n\t\t\/\/std::vector<pos>::iterator it;\n\t\t\/\/for(it = stack.begin(); it!= stack.end(); ++it){\n\t\t\/\/\tif((*it) == pos)\n\t\t\/\/\t\treturn 1;\n\t\t\/\/}\n\t\tif(field[x][y] == 1)\n\t\t\treturn 1;\n\t\treturn 0;\n\t}\n\tvoid push(int x, int y){\n\t\tPOS pos(x,y);\n\t\tstack.push_back(pos);\n\t\tfield[x][y]=1;\n\/\/\t\tattack(x,y,-1);\n\t}\n\tvoid pop(){\n\t\tif(!stack.empty()){\n\t\t\t\/*POS pos(*(stack.end()));*\/\n\t\t\t\/\/field[pos.first][pos.second] = 0;\n\t\t\tPOS pos = *(stack.rbegin());\n\t\t\tfield[pos.first][pos.second] = 0;\n\/\/\t\t\tattack(pos.first,pos.second,1);\n\n\t\t\tstack.pop_back();\n\t\t}\n\t}\n\n\tint size(){\n\t\treturn fieldSize;\n\t}\n\n\tint stackSize(){\n\t\treturn stack.size();\n\t}\n\n\t\/\/void attackField(int x, int y, int damage){\n\t\/\/\tfield[x][y]+=damage;\n\t\/\/}\n\n\t\/\/int attackDirection(int x, int y, int xx, int yy, int damage) {\n\t\/\/\tint value = get(x + xx, y + yy);\n\t\/\/\tif (value == -1)\n\t\/\/\t\treturn 0;\n\t\/\/\tif (value == 0 || value == -2){\n\t\/\/\t\tattackField(x+xx, y+yy, damage);\n\t\/\/\t\treturn attackDirection(x + xx, y + yy, xx, yy, damage);\n\t\/\/\t}\n\t\/\/\treturn 1;\n\t\/\/}\n\n\n\t\/\/void attack(int x, int y, int damage){\n\t\/\/\tattackDirection(x,y,1,1,damage);\n\t\/\/\tattackDirection(x,y,1,-1,damage);\n\t\/\/\tattackDirection(x,y,-1,1,damage);\n\t\/\/\tattackDirection(x,y,-1,-1,damage);\n\n\t\/\/}\n\n\n};\n\n\nclass LittleBishops{\n\n\tint numberOfBishops;\n\tunsigned long long counter;\n\tField field;\n\n\n\tint checkDirection(int x, int y, int xx, int yy) {\n\t\tint value = field.get(x + xx, y + yy);\n\t\tif (value == -1)\n\t\t\treturn 0;\n\t\tif (value == 0 ) {\n\t\t\treturn checkDirection(x + xx, y + yy, xx, yy);\n\t\t}\n\t\treturn 1;\n\t}\n\n\n\tbool isAttack(int x, int y){\n\t\t\/\/for (int i = -1; i <= 0; i++) {\n\t\t\/\/\tfor (int j = -1; j <= 1; j++) {\n\t\t\/\/\t\tif (i != 0 &#038;&#038; j != 0)\n\t\t\/\/\t\t\tif (checkDirection(x, y, i, j) == 1)\n\t\t\/\/\t\t\t\treturn true;\n\t\t\/\/\t}\n\t\t\/\/}\n\n\n\t\t\tif (checkDirection(x, y, -1, 1) == 1)\n\t\t\t\t\t\treturn true;\n\t\t\tif (checkDirection(x, y, -1, -1) == 1)\n\t\t\t\t\t\treturn true;\n\n\t\treturn false;\n\t}\n\n\n\tvoid print(){\n\t\tfor(int x = 0; x < field.size(); ++x){\n\t\t\tfor( int y = 0; y < field.size(); ++y){\n\t\t\t\tstd::cout<<field.get(x,y)<<\" \";\n\t\t\t}\n\t\t\tstd::cout<<std::endl;\n\t\t}\n\t\tstd::cout<<std::endl;\n\t}\n\n\npublic:\n\tLittleBishops(int fieldSize, int numberOfBishops)\n\t\t:field(fieldSize),\n\t\tnumberOfBishops(numberOfBishops),\n\t\tcounter(0)\n\t{\n\n\t}\n\n\tint run(int startX, int startY){\n\n\t\tif(field.stackSize() == numberOfBishops){\n\t\t\tcounter++;\n\t\t\t\/\/print();\n\t\t\tfield.pop();\n\t\t\treturn 0;\n\t\t}\n\t\tfor(int x = startX; x < field.size(); ++x){\n\t\t\tif(x != startX)\n\t\t\t\tstartY = 0;\n\t\t\tfor( int y = startY; y < field.size(); ++y){\n\n\t\t\t\tif(field.get(x,y) == 0 &#038;&#038; !isAttack(x,y)){\n\t\t\t\t\tfield.push(x,y);\n\t\t\t\t\trun(x,y);\n\n\t\t\t\t}\n\n\t\t\t}\n\t\t}\n\t\tfield.pop();\n\n\t\treturn 1;\n\t}\n\n\n\n\tunsigned long long getCount(){\n\t\treturn counter;\n\t}\n\n};\n\nint main(){\n\tint size, number;\n\twhile(true){\n\t\tstd::cin>>size;\n\t\tstd::cin>>number;\n\t\tif(size == 0 && number == 0)\n\t\t\tbreak;\n\t\tLittleBishops lb(size,number);\n\t\t\/\/\t\tlb.run();\n\t\tlb.run(0,0);\n\t\tstd::cout<<lb.getCount()<<std::endl;\n\t}\n\n\n\treturn 0;\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\ubb38\uc81c &lt;- \ud074\ub9ad \uc774\ub7f0 \uc2a4\ud0c0\uc77c\uc758 \ubb38\uc81c\uc5d0 \uc57d\ud558\ub2e4 \uc0dd\uac01 \ud588\ub294\ub370 \uc5ed\uc2dc \ud798\ub4e4\ub2e4.. \ud480\uae34 \ud588\uc73c\ub098 \uc2dc\uac04 \uc81c\ud55c\uc5d0 \uc790\uafb8 \uac78\ub9b0\ub2e4 \uadf8\uac83\ub3c4 \ud131\uc5c6\uc774.. \uc2dc\ud5d8 \uba87\uc77c \ub0a8\uc9c0\ub3c4 \uc54a\uc558\ub294\ub370 \uc660\uc9c0 \uc774\ub7f0 \uc2a4\ud0c0\uc77c\uc758 \ubb38\uc81c\uac00 \ub098\uc62c\uaebc \uac19\uc544 \ubd88\uc548 \ud558\ub2e4.. \uc5b4\uca0b\ub4e0 \uc544\uc9c1 \ubbf8\uc644.. #include #include #include \/\/class FieldOld{ \/\/ typedef std::pair POS; \/\/ std::vector stack; \/\/ int fieldSize; \/\/public: \/\/ FieldOld(int size):fieldSize(size){} \/\/ \/\/ [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":""},"categories":[9],"tags":[49,164,203,385,418,419],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/pXV5a-Ac","_links":{"self":[{"href":"https:\/\/talsu.net\/index.php?rest_route=\/wp\/v2\/posts\/2244"}],"collection":[{"href":"https:\/\/talsu.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/talsu.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/talsu.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/talsu.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2244"}],"version-history":[{"count":0,"href":"https:\/\/talsu.net\/index.php?rest_route=\/wp\/v2\/posts\/2244\/revisions"}],"wp:attachment":[{"href":"https:\/\/talsu.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2244"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/talsu.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2244"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/talsu.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2244"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}