湖南省第六届省赛题 Biggest Number (dfs+bfs,好题)

时间:2023-03-09 21:31:45
湖南省第六届省赛题 Biggest Number (dfs+bfs,好题)

Biggest Number

时间限制:1000 ms  |  内存限制:65535 KB
难度:4
描述

You have a maze with obstacles and non-zero digits in it:

湖南省第六届省赛题 Biggest Number (dfs+bfs,好题)

You can start from any square, walk in the
maze, and finally stop at some square. Each step, you
may only walk into one of the four neighbouring squares (up, down,
left, right)
and you cannot walk into
obstacles or walk into a square more
than once. When you finish, you can get a number by writing down the digits you
encounter in the same order as you meet them. For example, you can get numbers 9784, 4832145 etc. The biggest
number you can get is 791452384, shown in the picture above.

Your task is to find the biggest number you can
get.

输入
There will be at most 25 test cases. Each test begins with
two integers R and C (2<=R,C<=15, R*C<=30), the number of rows
and columns of the maze. The next R rows represent the maze. Each line
contains exactly C characters (without leading or trailing spaces), each
of them will be either '#' or one of the nine non-zero digits. There
will be at least one non-obstacle squares (i.e. squares with a non-zero
digit in it) in the maze. The input is terminated by a test case with
R=C=0, you should not process it.
输出
For each test case, print the biggest number you can find, on a single line.
样例输入
3 7
##9784#
##123##
##45###
0 0
样例输出
791452384
来源
湖南省第六届大学生计算机程序设计竞赛
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAsgAAABmCAIAAABZQPCWAAAgAElEQVR4nO1d3Ysdx5Xf/6leLkyGYVi4DEJhbdoekGUUMGuQIXpwL2hwWKOsE7F2gtgGLax2RaIsZldrsY1jJ7bBEbGCo4DMjXEgSkiUh8EP87IMLPetccLuQ3/U+ayPvn3vjKTze7A193ZXnTp16pzfOdVd96/+V0JjMBgMBoPBEMT/SfgrIxYGg8FgMBhGwIiFwWAwGAyGyWDEwmAwGAwGw2QwYmEwGAwGg2EyGLEwGAwGg8EwGYxYGAwGg8FgmAxGLAwGg8FgMEwGIxYGg8FgMBgmgxELg8FgMBgMk8GIhcFgMBgMhslgxMJgMBgMBsNkMGLx1OLw/o//+xePTloKwxOJ//n1h+/87DfLkxbDYDCcBIxYPJ04rC/P5+WdRxt0/R995+ze3u6Wc865rd29vb29vd2t2fb83Ks3Pk6WY3n02e03L56bb8+2dvf2dnfPvFLdPTy8e3X/zBt31z6Ww/uf/OrL4/6v4y9/9cn9w4TbJhm4jhNViS7Vg2p/a796YNzCYHj6YMTiacTh2xdnu9/6YIiRy0fvv/mN587ubc9m22e/8e3bnx+H7paxPPrs9ptX/mMRvOjo7YvOOffN230Hx/ev7c+c2ynro2gPx5/fujSfua1nX7vdx/fjz39wcWc2m8EmJxF2efTZu//wwlZRwUvq0nOD+fbM7aYzs5UGrmNTKjm8W71yZnd3b293y209++qt+77l4/u3Xj139rmXLn7j7Px59M3DmxdmO9/6wKiFwfC0YVPEovXJA4qqwh90n3K3tqgK58p6pc5pexM251GX8gC6IQDw7nuhakEp5HJ4SdedeBe8j4z5qC53ZhdvDTHx6L3L8/1rvzhaNs3y0Z1y1zlXXMtINZePPr312vPzs6+89e5nR+HbPnp9h85zp53zNx4G7zy8e3V/5mZff/19Esvb+2XNjxH2i3/727357u7u9sw598y1B+CrunSz2cw519Kv2GAhxg9cx8ZUsqgKd/bye79vmpaTgsYX1/dnrvje/eOmaZYPrhWo2+W9q2eIChtpBdalICy+jK4hb+PwG9+K2KTWCltRGHJbvEUwqAQvI8qiNRESofteFb9vrf2yLttW6f9DTQe6JgPN8q516VTXnu+mU4x+0EIygG/F4iRZ8bq0jsRbSzRbGRskFoOi4L/5VCthMrr807AuXlGXzhVFoXIj5PKIMSRbB72VmCe11mGseNAPb5x3s4tvD0X8P9684EDq3Dm8S3cSoubx7z+88eqzu8++euPD36ZE2bbtOSrRtyE3El8f3rwwc2524YawbV+XtMkphG1FZcSChck0jB64js2ppLOIr33rA/BXUS2aZvnBt3bgcvzi+r5zX7v8/tDUL986g/5uFI+sc231LvpNSiDmjcKrlJuCPr5vYlEVRVVLXKFTFuERRVVTz+eFq8v2+0FWLQ55Xzl8zflK30vbSF26svbtLaoi6npC/glpVOJKSTdmdald341Om6wo95JlBNqD9yZa8Zq0TmQ8jdTixCoWdKVRG+SVitHsLIGq5JocxmCAmEKwr4U/0wsy0SuZZcvE4o83Lzj30i3/cMAff/jSzLnZhZsPh3YcDakMx5+/+9YrZ9IpRdM0wn5A0yzvvjF3DhEd4b663HHOnbl6T+qpLl2k4D5G2EmJRf7Aj+7dvBLaqtmoSg4/+KeDgyvdLse9q3Pn3OzSneOeGwEOWpduYCBNf7X/W6rdMT9QVAu2ZstK9Z+dcbcRXi1JtAsusWIRvcyL3xELQFHAYuPugFwntdi34NuRxVEKkoQsefk08en40wbfBXF4Z1eD9nKFHHaQrQUdNrutJRVVP27JT3obyfHyRP5B5GQrXofWM1V5Yji5igVPFwSVa1Ayi1iMXsccEEMWVpNOLAYuEK/RxWgVy4gWMrE4evsiy2aXR3/6w5/68NIWMNrAIWB59Nntb78433721Rsf/j7zUQy2H9AW87deeCv4EOPDG+edc+78P8tvGRx/+Yc/fDm5sAqxOPv3P/qv6srBwcGb//pR+pMo+QNfVEWoanQiKmmapjm8c2nHua0Xrj9YDnyJEgtIW4/evujc2e/dH0aFSncwfKIruoXq16vkGLybL2vYsr6Y8isWsZr1wGfaoURCAsxUmZSDcCiulnV309BTF4ayiIUfjSPOCvCcQZ8RVwT7Qz6mqBZ9Yh9Og4JpdqDqQKaI7H54ydsvWA95xIJeDdPHNCsGA5pW6+yb08csTrRiAaMfXMF6/A9ZZJRYaAx0Bfg+MV2QLVKSwn+kO6bOlYSkJdtLuDhMPUGo/N5KAZ/shF/+8OX5bH7pB5+MCElN8+DaM845N7/wdwcHBwcHF8/tbu08/3r0UYWW6eQ99rG6sAqxcLuv3PrVl8fLR7cv7bjdsk55KyRn4F9c33ezr1++85s7pXvm2sd3q5fns9nl98hVJ6GST39wcHDx+e3ZX5///o+72zuLZcQCau2j13f8FdQl881D5pJBqKAVTUAsKn+bv4eTgkxiEaAKYDkVVQXyA6FLXJ7sb1crFp0Y3jHCbfoh/5KzXLbD4ruvSwfqCm0PZQHVRrZVwwPHlyG90UDKEPDiisp5CajzvJqcHS11NN6vULFQiUXIiteidUHQU8csTu6tEFJEJMQigJE7Siyg8+lI3DOBxS+0v+ibW1QFeMCtKgLia9aObS5csKA5C+ET8Ou6dIFUeHF9f+a2XqjuK4Hn+PPb335xvvX1y7c+zX5RsiuFlPWyaZpm+ejjNwrndi7dicXm9y7PnIuV9qcWViQWv/v5O75M8dHrO44+PyAja+DLRx9XL89ns9nMudlsNptfusUJyMmopOkf7p3NL739m2UasVhUhf+A53oNMfShmokXXFGWQWIx5IwaFwhtKsB+aDqsFZ8RsVj0q1NuH3AjVEiU0Q+svWzoCjIKrEdcHJArFt59oMpwWQPaklAy5XutRVG0fGeI5O2A238qTeqdSfk/+DOJGeiuUrp98PkCg4UZIqiOpFrxmrQuj+u0PWexEWIhrbc+yVCIxYiKRRD9BKmuJY/ycRMVjBa6G6WYEXiiKJ1YeNeKrTmXWCwfVPuz3VduRUv8x5+/+9bL862vX8qppi/rcuZQmZxUMjUEn/l4eOO88pzBSsLKxEK4AD5PoGDEwI8/+e5Z59zXLlSfii+jnoxKWnTVkvnVeylbIYxYYCcgJaJijT9SsajpemFtSa3oFYshqmvAxAJGDq1i0eWui0jbOFMZclvcPt5YLgpgTjKxEIcPvo9EONH7LKoCPGI6DI/eJ7itSG9hYrFC8i56bbR74oi8wGDLum97vBWTbsdoXRvXU0ksPESuv/aKRW8JrIw3YQEpQKbRV5BaoCyEArtFnJaQC1tzX/SJHvaODTY8jVgsH1x/YXt+uT2Y4ejBT37yIHa+Qvv833ZqeGof+gPV+y7gRuegjWR//cZd/tXyo9d3tecMVhJWIhaL6/szN9u/juva8bdn8gbeVSy2trbcbGtr5kSit1GVLB/8+5WDgyv/3svfrc5nrj1QHt5ElZR4xQJ9QxO/Xk9SQoCJBecRsecjtJUnZ6Fyw6C+IG9OuIFNgFRKidKkWoIcBbrTC1CX3YOtVTXUQ5SKhai9nr/ArpJQVFVJqJR0q6a/GLGQm6GqC1ageBeZWyHC3b07TbPidWhdkv5pJhaL9gkkXHjqCG0gaLIUf1zXBX3eqWv6BIgFpwhJxCJNE/gakVgsqkJ4xuKwLuc9q2ia5r3Ls9TTldo3FrfnL7/1brDS8cX1fYdjTve65aU7y6ZZHv3py+Pm6N7NKwcH//QB2SNoX6zkr08e1uV8/5q2a7OKsI1ELD563T+22PR8odOkInnqwMHV//LCbOvZ125/fts/Y7F1+T3KEzapknbfxW/l3LnknHM7l98/Zq+bLqqi+2ZA8BkLMZnFVf0uJY5XLCJFBiW8MiRtefOKBXUywzjAkP0+hmuLDHLLZenQiAf3MTgsQjBQzUarWCAFItcXdSwhR0mIRRqziwRC9etOEzV88kb3uRMTCy9VhhWvSevjL90YNvxWCNwyZDua/hvsSWKFJd9FoJxxaogFEzSRWAjVRr5bEl/IyzuXaK67fFDtz772Ny+3jxYeHBx88/mdlFMQAIbw9ENFocILlyC+Prxxfufy+8ddCOOZ+OKHL+06t3Phn3/RPW5w/PsPq5fORN4mGS1s00jEYnnv6pnijbuHTdM07cObsyGGq5KnDVzpPlQN2ZxKlh+9vuvml/7zt8umaZa/uXFh5tysP6x7cX1/5p753v1l0x2QNcPHeOOXkKIumcQpH7Nrddn7rFUoxI+rWMQawBULsXdtcICXiLkuvhrUM6ET8UyC5Q3aVsiirhek/0FQ8ok03GmJRUTxoboEjgxrJhadfruhMDLZf6Fb8bq0nnplQjfrwmaIBSTpkUHCjSx8qVyKQnc+HsSiWyminSLxhMGgJIoYatLq5+dYtCk1wahjm2j63fb3o2+2B2A759xse7733Pc/ab85/ODb5+bbszPnXjx74a2PHy2b5aNPf/zOd86LAfXw/q3Xzu3tbrmt3bPPPHP+4ptZB1+mCts0TfPTK3te4PYA7ys/7YToTraeb2/vnnsNSCBJnjFwjqN7N6+8eSe8o7ExlSwffXzj1XO729vz+fbW9tlXKrh3cnz/1qvn5mdfvPjSc2f5r5/cuzoH1RpaumYGjpJyuH3YPSQoIJhprIVYkAIgDPcqupoK2QoJ5d50kwF8TTwXJRaka7QL67qSiK/g+J0mTRchPY7aConVLIITRxmWiikqFrjCDppJs2LQxKRa13uDAJWszRc0NvXwJthbCplC7adeuHQV9SyqbiMywxBz2x/XAvYpYHUm80zNckSy3J6BcPHtVX6iYo1YVEX2W5SnA4+v5OvDL986A7dG5FwPrXSyk9D4O5U1m0oswq5H9ANECmk5adwkOSz4Rsn1fCNTq44kVCx44sGDGvNg3hWFw3x+xYIKTRHes0JbbzkVi4mQY8Xr0ToWJq7HJ7ZiYThNOKrLHVSzOD1If/TwtOHxlXx9WN67eib/sA3D04FFVZxIyHuSAHdoTheMWDyNGPu7k598/7m9IJ75x5+tItcn3z2T9+jhSQqLO5tS8rVhoyppHt68MDvzxt3TrhSDwTA1jFg8nTisL89344dTGQzjsHxQ7W/rJ60ZDIYnGEYsnloc3v/xOz//3UlLYXgi8T+//vCdjB9TMRgMTxKMWBgMBoPBYJgMRiwMBoPBYDBMBiMWBoPBYDCcPsRfkj51Z2622CyxQMeiSipJfdkcHKPbNI1wkoPwHjP9KPAGsPCVfCYE+X7qN3/Uc1/7t6fBuXxUJTIip+kSPSYerRJ7lxrMkj8ZaMUVMaaFgJzCIaaR1SscuR6afv2ckyybx/elKyD9mJXkExhSWgocuKDflNR/zqk/Ux1qMG51RNGqRTaDtoPEn5IYpKGzDRWgToKqJc1A8YLpzxiXzDVBU9IQ0WkRYzS/jqOhAsexrn+OYqsz+fXTlKW4EjZKLDCvyB8XuYseVKJNk/JRcPb4SqeXJhjSikZdlw79Uo0wmkV33LEP3dE+gyFGOjNOGhHWHdEkbUQ5YnQVKhZXPjs0ORhfFou6KvwkM5oh3Yfkj7qw9MieemUOA8h5330qn5NC9rX+o9dlhYy1EIvA6shDp+8Ej0VkUfqDp5ficz3xib+CHMEBCPMydAWIhf+/ukjLmmoP/D48a1v6I1HzmyQW8qUrzVHymW4gXQuDJ+IZx6VmYZPEAp3XGxq2hhCx4LGOtkatTF1I3BwjxQ2Wuk4wNcMylvysRu/p53wFq/ZGaVR3SCk65Q7T7SRiAZfhVLlw+Ox2BCi0oglJ8ACxSEtMuHSTEItUTxP8xW8IdQGsOFGk+6JaCJrruF+ynAnXot92SLkuEXmrI1dVWrExeLCkTnb5WBdI3HBU0bQ0GAUuQYrEAhgQvlo/mlNzaVmaz7GQDGiZUhgTzRETRa+5Oj2Eovb0cDbejCk2Ryy8zKLS8L6GbA1BYsGKSQnEQlKvRDPZpWPL14kgbEWhKq0Qsr1ANxBZB4QH+OIr+N1ZqpRUYpGmpxwt9WYU8CHsMOh+BOqh/uHShp73ZKTCU1csMrqO5W1Rd5xvxVChraRUCG6XUUuNjCPoLqetWERWRwZQETeVWGS5/7pENU1dTyEtKTmcQizqsp3wmEHB+mpixSKsecHIIkaXBE4s4OBkpU02R5HV6VP1WDbBkj3utifczN8UsfBBsHP0TdOQGoaS2YKvIsQCQjAhGlpEd0CDNZOBtBjIKMbOkZ9gYJxSZPf8vVtkRVF4TfGrQ8aGLyNRlmskRhgEtcB5Xx145WHfInXjPxbu7DZCfE2SyD8s2GFWMseu3aWHjaJwwVWebGCrbWyMdTaUWBRFIFlNFfSEiUX66shrEphd6kJiYghS9qDPPqi3BrQkRqy2HMqJRTW0I0wYqWD6QWoVCzSmmObXRyz42OUekHCTzFHIvZHeAwsEVan6OSPVovZ30lbewW+xGWKxqApXlqKZCaOYgFjI9F+wVubtRDkDxQ0dQ8UgDWXNZMIhznsh/3k3zr4MVnfBO+6koUvzw+me6Gg5AFjO3T8Du7MBcw/ralzQg0axWOgm0g2LOBeRsHd/xtJ7JEPGEsyrWPjaqE5TUjQXJEHxShZNB5MtmVcsiL74ADRRUeHOp638mqHJ5DJZ1tocvTqCCi6KXimJFQufsrf/Dd8TiKQrFxMXi0UtViwGsWT9gky8KzpE1kW65icnFkNfWmlF9XWTzFHfWOIEpVQs/DXlsE9OupdiQzY2QixagwBzQIyKF7RWJBaS36V9deQak+CyvSJSa5dz5ZgAMXATFIwSll3UhCDSuxzj+hLfQF0CBicUREgtiAtWVFXJQ0m2N07zh154OlhxZAk9gMpRArh684gFLFsK4galQLxUlKWJ6X61PJwLSNe9tHalxcSyNRzG8EgCQ0pni4EBJa+ORCyqsnv6OplYDKbhx0rpn5gN01q+rKe4ltSFjrdCQL6jVSy8CuuyzYi0dZSj+Y1thQRanHqOMioWqPsQFosJahJhbPDhTZRwDBofMm8UMLOJRSQdghcsqqLdQ2hDMLM0ZbZGVixWgWYkUugDZgjqzulhuIKkSrsVfJdFLDo1I22nR1pZMX1LuHPqi+nC792YMDl9Q8Jk6x6eQnVdI4mF9EFKgahfURr51qOwTGUyIVUs0DdMLjHcrUQswFUrE4tFzurIaziZWEAfyYx+mDJR273gNMI1aVqS/VxRKRWL4f96xaLNM/SKhZcqS/MJtH9aYkFtbg1zlFGxCLt7QUla1W7VckVzAsSC5mMoNwMET7IGmVhQT9jfjkyILFvEaFjpPJVY4JummA6MQDCCQiLpEEXTGlW/xwuYBdNxxAJeDZfP+OCF4tZiARpjvljOYIT4H8p8GW1tn4GQMTmx4IMPpmV0MMnEghaWV4BOLOQP5TFrDIo5CGneoAjshnFLNXF15ADnO7qLJ/5Fdlt9tZLpRnSJ/V0ZWkqtWHhiMXhZX/Ej+WOfCsnwt6VofnMVi0FXha86rWuOSAvKBf3qLZlnRbU0tbC2elUP4SQqFsGPmkjWh10Hm4q6BPMUoJmB8kYisQBG4qsFOpcdAz3E1DXMB/BgRJcQHotvd3piIeam8fAVCq8JdZiiWkjmgiyCkf0hn1CJxSCVtgzXUbGgHZAegh4hjVjUEz611TcYJhbURESDCBCL2NW4yYmc5jhiEZzPpIoFt0h9EQezYaHPLC2p3QJCAWKlIpS/By9WLje8dgylS5736JpTQon/ZE1zlODq+iorW89FVQVfQQ0McnWcRmKhgntDxiloEYlFAcGJ8VlJIBb9VQGDGpnE4JZCLsk554qyLBzgwX5968w2aQmFSo5xcweeC9Wk+pUgFGVVSXKgsB9RIZBpgGkMp47g3sBCFwWbwMlJhZ4YsYgJWvs3+CZzLUQ9odRXTaGYIiImgSl+71b79TA9sYiZSJLY4wsd44MWZAF5WkKjJlODKhZNuITfe2Usm5ajNWM1nz7v4QvHfTvJHAmdRdNVriEmXz85uMcngFjASlLKjQkWJHn0RVXgF4Qlx9xdOLTdyRlwye3DRpD1p9l5LrQQAyhED64AOlQvZ9oiWaHYS0hX3zNTfKC+kudw4RywXkiFkt1YVAukrFDFgg2Rwi/8kGMN2opOLDox4rQOFc7CXm9Bn3tJljMEuWIBVeIrQIIhy50qOgdClzW9LjAL+at01OoIW3L7bXhG47UcoTscOogaaCALaymwuvxXg+oV95ruOiJTv46KRUy+8PwEKlWrzVGiC8FbKZpL6a4sYb04Oz1KxwaJhcGQipWLPQbDqYBZ8umHzdH0MGJhMBgMBoNhMhixMBgMBoPBMBmMWBgMBoPBYJgMRiwMBoPBYDBMBiMWBoPBYDAYJsOGiEXo9dvJXqBV3yvsewenjqD/q9DfGOrbzXjPPhXaORpVWJj+Xv7SETreKfBqEZ4k9iqS0CDvW3sfMPr2UqaFsI8inUinJdTiT/BEmlqLLZHfSUsxPHisUdKLYlMts5Q36VPO9ZEPtwjOUfT1u3HvyE06opTrhtEDo5EMWtJQ/3K0os7IEqfDBS3Bt62VxpU7mJpWszP5zXmpT+UNSzgCSRR9vqn0wlu6/kphyYbeaqev/rNT7sa5ldOKjVUsdL82XTx23a/g8S+H18XRsRbMn4s36tLRE9n05ZgOvK7p0TF+TUSPcfI/NIOIBT1dEvyr/fFwlWbA0UgrZTiyQjlKTA4MwYPJ1G+S3LBwxIFwlAJDjAetw5aIr4uJoLrGwI0TLTOqaDqng1UNV4nD9heMmqMpMfmIwn2p4YkvMc3o4+tBkBDe7Zc+4DWKrukRL/gQsgW/eLVJ68yBnK0i9el/9ht5HTpRzG/h5oPSh86+wn63PaYQfaT8DkfrJcWzJsa5ldOJDW6F1IEfplnViwxrRFrzUpcS8U89koSfaFNW7d8oqR8zHHQbYhFiESMvzyrKMkQshk6J/8Efg5bBuS6kcAM+CB4Tw4/BSbAQ8j06agbOpdi57CrSD7Nagy0BdYbS3dA4kU7TD+gaaaA0a0TckIZhaUjIt6bO0bow/YjSO8P34C9JezC+ByoWRGqgSrawYYuNpnW0SPGKFdevntslYVEV6EcU432GPibfdCMk4w5JL+qkozFwtvomGeGvh5/c84eS8V9y7c/e5hMqk9zHAafgGYuV/QhJkxXDaf0BtlFgGMGT4xRp4VrtTG04BG3MkDrJ/f96wiJ4kDRi0Y80oWLBk2biqpQlJq2Usu7rmaDEx/ZZklcJ7hwK2kpJhUM5WV7QSis9rsGWQG4SlyG1YgHzHWK42S5KiKfMl7IwXJeuKAqcfpIS78kRi3WNSIr8oM4YKKiTbJv9u7s9XLFQ2AolFjQYi8E5RD6ElKRzgmNnr7sXdxrsMyS79o0cHyTppWahBJ2myUdUJwxlXVee62BziLuVxwQbIRb9Ch7CG80QVvAjPkQBM6CRvRVgCNOt+/D+gaxvNW9kOTtyGuDDUeNhNTzfsMBUQsktkTeJWHQbIcDb82ykHW2vRWHJCbWi3pmRbKs7Whb2l2ohlFigBAdfgZXUpQCBydGzfLzaJ7clUWk6waCxD4Gao18T3gqKql6MWXKID/SBVgvDQ0W37RrZtFYAUOcosaiUndStYURSvEgjFmTAWjkqWLHQ6u+xioUQReWo7CtinFaMLtXC3mjkV/ukfcvfCE6JXS1LH6AxOVbYzwime4Qg5rmV04/NVSyAarB9kFQq3X2Q6MuNYkglsKeuu620uotf8eTfN+ZRl13drDUSQDO6f44imL2wJHqWNQ22eRWLVjKp/oEkVTMiqU2pVAdQwH2DctgZEJwlI0DhfRhesSDrTuJPIYG911LiPY6CU9sSI1VSqEJXYuHDuczQSK/EVXZthRkK5/fDx8TQ5IpFfI4wJihtrGNEkxAL9tXYMmjb2sKX9WBJbWhRSoiECMxZoP/YL7kxYgJhBMYj9Am+UPoj8UEdlio9MkR9UKE17wsh9AdQYdF2Ardy2nAixELZUMhtTqggBKpeQjftEotMmrxS6rJ16QN1CYbMPGAXopTW00xNDVqRdmRSjhd1QsWiaRrwEGmCsCkWQuIOzNRoDBCDFv+u74Lv6ShuZVpbgi3q2RC6L7Cv0X6VyNDz7FNifnoY9s+zocpb+0k1Yo4a+lFCbeckRjQFsSAX1qC+l1JW4y3wikWDrM17M9gnqwQ6fC/J3JqxxAL1xf4Q+mTKEoKBYz5ZGlea9EMXKeWKTqMl9Ei9cdWwJjEQiMEER7mV04gTIhYwcZog7+g7EBuS87yha1BJTzaasqpKXLOVbh0zKrxGSJZCUoywmxFyqbR0ui8GcY8uEwtcNVAyO1LBELWUaCFSxQJ9g4kF7kkMWmLdQxz6Omypj2asa0kcFnslYsHnWKjGjkDbCnZ08fy+0wRz/Hlz5HsQyadeDd/8iMYRCzTb+LoFK5yzUXCmQxeZRCwgBCIi8Ar4SedwFQ+UYWraWilrrU9JBVQH4SJCg65NkD6FMTHVJvB7ja3IbuWxwYkRC49wKTerg8DKQ14B1f6DvQdjMSYWup/JGAB2J4E6nq9sKwWHdGLhPx7+lU4sUBQgH6lFG9lHJlqITizYh2yCgFNRsuHA8ueyT2dLNdi0D4lQ+yfb+w9ZFGPVld5FdzWZ1VYbTrKSNg7AfSD3HDFHxG4oyxg5sqlHJMWTILGggbC/XeJUwVAFJUypWADEeUVakB9XsVD7ySAWkKiGJAgZSkD64au0YqDciu4CxruV04nNEQsWTPwETaO2QJ25hi//4bxAN4LhkomJRXDpAb7gHa9Qow27iTxigYgArd0pAxoCIQqHwMkG51QmFokWEiUWwnhAg7CsGhyi/PmabCmxYrdDQtcAAAsMSURBVNF7TeqGRJfWfgFcNLCowKKLhAbIaZpYGCYXC2NLn6NI+YKab2Qy1jci2gS5iHBkybzbD0i5EnkbvL2Y4AOkq/0T1TzYitEXxzgqn78m5N0SnD26SusTuRggSpzYpBMLoGYhvMvUS/av0KDFxZrhVvKM+6SwGWLRTksVnfOVEDSpvnrZbpOWNfS6w1KW79NFxsTCUSSUTwQpfQmMB/n+VnKdiGRiIZUp5NQZ5gTMIaroJWS0hAqRaCFkxGLOJJZdsCfIIBZCAJvSltqxl5JOBC2R92lkCGkb1XmtPasasE84um65UftT8ntwWT831JKH6+Q5Epw2k9RXAIpqoZj7ukcUBBaJhiZSOiGxGyTldW95qmrIEiYEBdYDRGNSfSlsVb0gwb2FIFUphD7lj+OOOINYwLakW+hgk4hFqG8XdysZxn2S2AixAGsuuZI3qhexBZy4eSmCDN3bVDh5y69YpJYycP4F9IdOZotkK/0wmCdBGCw2KZ1HPCU4mxVMjQMzX9Y5FiJXLOBtRE42WdEh+luIEazDlnzuFVYoOZEvoiWGAF8IKkEd1vCpnN8H5PNS5s8RblyncLoi1jsitaPINQojxQuD3CykuFBMbt1hra0daiHn8QZcixohCttNiYni0KjoVqxiYRCQlNgYDCeEaewz2spjtwyevBFtHE8orzBIMGJhMBgMBoNhMhixMBgMBoPBMBmMWBgMBoPBYJgMRiwMBoPBYDBMhs0RC/z+ZM4z1SHQV0HgI1T0mXL/MprWufYcL371HD0zzt4FER9QCj7EHzxRIPy4kzBE/rY1fb8P/Z+3pz67HHqePXXykh7g4m94RCG8Xzmu9+G9D6wK+bwEfFeo6fjr9arEBfm9R3GOWef6/Ka8gZl+AETsyoSjC7xuFPMD92e/ZYfeG0q7U7UlPhZFHPk9ge5i5Z5u7OyboAK7L1Pf+Elq02BYHRutWATsedQz1TU4CcmfsdC/5cvf1in6A3D4a1vsLTftklo6pSo6CnXlBx2l+qXIU1qfxbtpP1xUBXlfUXs1V+xRGVnCKRrshqhHW1QlensuiYkkWY/eu/xmqX8NVCIWIbaIXvbVEJV5mDr9hB0HfsECmcKiEl5glOY36a04/zZ9DOK5IrGR6tewkx+E14uRkKIKuztSgqlqS6xH4cdlimrBXAQ6JwMSC9ygrqKYjwBHdyTjtB+DYHjMsSFiMf3LWpI79Hmm9yUDHQif5SAecwJWKyMW0jFNrGXsXzSMqVjUw89i9DFO+g2t/igJPlb5FKCMioVA3YaPxdgyqHSIuUmOLTHjzS4TkaEzx0xO9ZDOj/AHdIBgF64f4Q4Ssv02HYWzM1jfUP4D2T7prY4cFI4uZ8GdqR6f9COc3KQNKjTWiB4oq5L1KRQug3Ou9hjk8vwHKmk1Sb0RtA2JRWJsD+rIT3IWU8ilIgZDBjZNLISMSzrNyEM5OEZCXeKzo8BK7qv/ct0QfoIFgU6AEQtyTBNtN1jbYB002YFQ+qauvIcnBWR6PB3olVVrRTnx7XiDxXeiRPiCy5U0swnpbsbJT3pQ4fokVBN8pKSc/N7ViMUQMNRjkfSetaDFJUo+xSe4jSnojHWifJlOLBRSKtmRv0SoWASSGE0YTC2HZuSKFmtyZWIRybvq/icwc4sWxiwMa8JJEAvsFEYTC+bjJGcvxMxgxULbZIgSC/4LdEO+mQZlqzaWDBF/3no7wpSca0/L7rupy6KQneKIZyyGW0JRBTIsSngC3i1lJySRV9Td79yXtbgJlJO/cbap/HOVrRC+C4JGErinaZp+IyRQOloRSsVCvdgVhV4KSCIWYAUSJi4ccj6SWARlGTWb0IJxA2WdupsT15JPmXIm12oWhrXh1BOLhDb7lmIxePQqWiz4jw7zioWQ1uPNVfbvWLdVobsaWJpl+9DIlyEF193PEdRdurVKpOkdI6BrvCk+4WK5Xms+5TGE+AD6PrrehS7JR4LPJzNbVUX78x5ks6moqsCvfqeMu/9WixRJFQulh1G7Rn0jicUN1n4dfMIwkVh4CT1bF8oU3tqDMsbLh1HguZFHgU2YNl+X+BdiQj4wJprOQ4P3TMMyDQaKx5tYcI+GFnif8cNKtu5CUf+CE4g/YwG6RCOikvYpVsAZ9yKUWmhB1dWmaeoa1iQGAqFufQ/lU1BoTgHYsxcTMTwkad+e8TERqUww6h1hzuh7p8UgNPqOgSEqQSpA9Bq1YjGKWGi7IGQQwlD5DeF59erISeKFXb9gSBTXfsK99Cbyq546xlUswraUSVbwCiQN+NzEz2ZwOcRJQNBmRrZpMIzE400seMUC5KYge9HzpQY7atkLF1VaxQK1R4gFqViA2+VA0ftjZfUn0ID+7kAs4fs3VIRIliR5VJw4cnfbEaEIcYhtAyUJSbdakKrRJhs3DxSbkPOv+7/r4V1Q0VRW2QoZKhaZTIEGMqQaXVfJxCI8pNgek7Kzk0YswLip1ln/ayAWUr0haHdSuQjWzbwn6D+Nb3aosIqF4VTh1D+8GWwTtwQrplI9VnNHKU45g1jwD1nFwrsVxZ/ATD9p/afFDJz+VYWqJ1FsoCG08YFJUrzQENziyYbqkIfxqWwR0Buplbp04i+5D1ocbMqHLkYsRm6FgK0rdVrRFyFmRK8Q96Oi62JgaZLkPrDB77iJcb6YSCxo04H702tv8bayWvXq1R6ZIsSi6DZQ8ZaI0nuEhms7Z6PbNBjG44QrFvwCCm2VRioW7BIYMBfUD0UfDeBXR4kFidCkYjEMTUtJYecyBUAyMBIwjLuGD5Di5JF3j3pKz2iGDmKOShsygzZkuc1Ud6pfSngnDBHsFk4skNqnIRagtq1PsgZxJYQeCej+Fupodf8iMyr1ICbVtS8SM5Fwo09ztkJ0NQUuyEGaLdWl45uUqBanbm1614HrYBFjDw8yfxck3qbBsAo2TSw0qFa+ErHAjrL3gXVZwDZVYsGCNLyaJDBSCideOFzvT50AvevJvFQLIMRCc039UwFlP27QC1RvmxQOV6URC7VEJF6Vtf+byhfSPaQSN4bJxqEXKkusZskd+05W2AoBLUlrh0ZnlSpggYlQbJ8EsweJSoC/8BIpsJBqgaFrILQJRUeKu6aa0+/v7R6X2Ub6IdgEzCyAFhAbxUBEou6erRhqZq59/lo3+KBUY3ZB4iM1GFbBCRMLvizz28TOhixrSB/UiinywKLXhV8B78BGB3sP7OOWJRFtYBpBLfQxjp+EpQCwBDxsXp7GJX+97ktDSmTjN+GqCZDqJGMVi/bfUlCEc+SArVHCgWZ+tYpFA/dDqImGtrDIn4TewJYKcHqWsJEC4J824Q0N+ukvTGCFXseyHphjQMWjwLZE6Q9jpyNaLGDLAdYjl1mI2jP3HcD1dfs2SPsGOJk0SW9hzjDsgmQ5UHu+wrBWbIhYGAxrhVx2f/zh9yiexNGdTpwuW9J2VoZvC34232ptGgwrw4iFwWAwGAyGyWDEwmAwGAwGw2QwYmEwGAwGg2EyGLEwGAwGg8EwGYxYGAwGg8FgmAxGLAwGg8FgMEwGIxYGg8FgMBgmgxELg8FgMBgMk8GIhcFgMBgMhslgxMJgMBgMBsNkMGJhMBgMBoNhMhixMBgMBoPBMBmMWBgMBoPBYJgMRiwMBoPBYDBMg6+++sqIhcFgMBgMhmnwl7/8xYiFwWAwGAyGCfDnP/9ZZBVGLAwGg8FgMGTgq6++0moVHbEIfGcwGAwGg8GQBSMWBoPBYDAYJoMRC4PBYDAYDJPh/wFhf2kfn78tpgAAAABJRU5ErkJggg==" alt="" />
题解:非常巧妙地剪枝想法,每次DFS一个位置的时候,处理它能够到达的所有的点,我们假设这些点都是沿着它可以到达的,如果当前点的数量+当前的搜索长度<已经得到的最优解的长度,那么这段必定是可以减掉的,因为无论怎么走都达不到最优解的长度了.还有一种就是能够达到点的数量+当前的搜索长度 = 已经得到的最优解的长度,那么我们只要在当前搜索的解后面添一个最大的数字 '9',如果这样的结果字典序还比已经得到的最优解的字典序小,那么也没有搜索下去的必要了,直接剪枝,这里的BFS按照我的理解就相当于一个估价函数,让结果一直往正确的方向走.很厉害的题目。
还有一个小插曲:就是关于手动队列和STL自带队列,自带队列在某些时候要慎用,比如说这个题,BFS调用的次数比较多,给大家看一下两者的时间。
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAeYAAACJCAMAAADOmGvGAAAAAXNSR0IArs4c6QAAALRQTFRF////+Pj45+fn///v6enp4+Pj4eHhAAAA7e3tq6urmZmZ9fX17+/v8/Pzz6uZvd/////f3///7////9+919fY29vcz+//mazP/+/Po6OjvZmZq8/vvb/BmJq9mb3f78+r372Zq5mrmZmrvZmrzc7RVJmLvZm9q5m98vPxaWxuz6us0MXBq5mZlLC1rKvPta2Z7Ovrx97hkpKSBOZHcJuvLyoyN6xZBO1KqMK/o1VWp5Zwr9W1Po5JDAAAB7FJREFUeNrtmotC2kgUhqegBREFRNEWBWrRhVpadNvdtvv+77XnzCWZG5NAIwr9fy9DJnM5M1/OmUmCeMM6Pj45mbXb7WazuaxIrSn9klpPc/q9qET/kpYX6meu0yVUQkJTnrUl4QNSrRK1prXWA6lKzH+TLmrqZ65TqIyEokyOvGS+h5XpaXr4dE16eprT73klYsyH5+pnrtNDqIQkZvLlo6o1b9EvaS71roR+fSd9ow8/v3+PV/iH9O5I/cx1+jL6+WHzur9+bt9eoZx5eSSgfZZ05uYBMO8/5vayBsx7jplXZmD+EzA3Dw6BGZihnRfvs5s1YN57zDPC/BaY9x/z0sE8vbY1xRTtBeYTH/PRNBNhPlpijvYS8/UbW9eHZVvqX57pT/XTjky79z23iDlRQmsULdvU1YfBlnrcCcwXNzc3i8V58+3b5uWlxlw/bbVaxLH7UU1V932rNaoA84QbGXPNcVZ9rUlXBvVvB2zTyEsX8mSAuauzaUg3vYIek+2PdhrzN9b50sWs52A8lEhbdNgf/j5mrlQ/5UmbDDfzLWXQhNrhC8VL5cmwqTxbDiTZY7L9Hcd8d3cnMf/44WO++nLG13GnoqDNHta9/9oR9U+DzTBLg9gi6axeKk9Ges2zr/7qpXtMtr/TmO/uDOb//nMw08iUDxiiHLs57nEqYzqlQyr8SGlHYrZLDLny1eeRGGfRknP6o/FITrcuy9UvZ3ZR0yDlyER1YzqTdPq3X4dhKk+a2tRF9+NDVkdV5P+u1WyJtub24fIs2b6Zg6EYk+G0AqmDXcP8+GivzUO+gPujHHP3PQ2pf9OT3k1xjBcympb6KY2Zs+97eQkdJ3lVyz2IYuJITDrkMf1R1pqs7hQ1DdYfzvLGdGfSIB1Ww5RPmtqMmZZTM4gMs2e1xsxjqp9SI8n2czMmw342AbuGOdtp57azixrMMmUgnNK/Pn+RQDmtnL/7nlOCPlwrz74d5DFx9mlAEZuWZlNWV7eK5t4nnVs1pjvTS0N/ob3MTfmkqS29eSCXhyybjzyrNWYzpnT7lhlsqTnYMcwn7QAz75XMfluBoYkymBX+ALMuQXkLtaCpXZe6ag5o8Zs80tybsrq6VTQj8HmYEchXDt68kUVqzfRSPhnBnGVHrPYxp9u3ItvtwNqfvH7M5wvWlDAvZ01/bVZ7kjFT6g9VmKVYpQOcDN4PFHUpzo2toK3OdB8lKVr9OtZlM7nmEosvZ8KUzaGaoqZBnsWxWiO6j7ozaZAqcBmk1kkVtA1mmd1Rd0qe1TxI3YkM2qn2qawxYzIcZxOwG49HZu32yWx2/Ia/1BtiltPE0WmUb8HokLcreotEAVdm21swOsOrLu93bnoT66a7r/ZUo3xDl4XorKhpkHcIP9jZuDGzH2ODJtwFzb2f6uigatuYZbbaNgrPal4YdCdyTKn25W5e1p4o9samHXjY6TzTPqqFd5JbfypQsKtJGrTiZLlBqCA83p3HIOUxHztf460dhw+G7nuvC3PSoBUnCwdR/9RTy8hLDHgLmLckeatdMsC9yD0Kx9+h2BO9GGYImCFghoAZAmZgxkwAMwTMEDBDrwtzA9pjATMwQ8AMATMEzBAwQ8AMATMEzMAMzMAMATMEzBAwQ8AMATMEzBAwAzMw/ymY1TfDXsYGp9+IHfLYzzfH1RtdtsX1eg7GlR2K7PwWvJk7qbQjsdG8RtDlWVZ+NLMaewsaFBthDkzNPqsPlU//ljCLzTH7bhvLt46rsbpyHw5H4dtvO/GWMQv55/SfTq1B2fXMIpD/CZOG7biYgww733iFXS45PXZsNwZ4+ZldkXFH14rIOMOgG2AWMcwrvbnSIG5jFvkUioaLaPWfN44830JQpl27mcYKzPml6JZLzYfbf2Ic3rynxumVE3bbCTuEu+h4F2l4uVfo3a43W27pD1H4W55wn5S52ArMXruutzsXcRSzFS68cunptdzTizL+ZfB7mNPu548rb9dbpDfb4G2A2TEjQjUO2p/yiDevatfDHJ1X4VwvTrmCmO0GUd/4Kr254AaisRbmSkGXwlw2aKeCZFG7pXfawcKQno11grZ9paYXpzJBO7KRdC5TH3M46GcI2sHOav0tmAg+eMHcD+LC2buVu292tlJl7qcKtmANbzGworqHw8OnywXtFt43R7Z4Irgqnm0LBuFhJwTMEDBDwAwBMwTM0Ob3zdW+oHq+1y0C3Db25q2/iFy3LwHMO4h53b4At0rMhe+brajsvI+NPZx2Hy42ghdxYnW7fvvR97yNyMNTqACzWOe9sEsyjrnofPrqWO998PN++2K/vNnsnSLvjWPvlwsw+l5YGnMMdzFmuPN6mH2qUdBRDCu8OcWzOsyAuSHmovfCbr6Ifccteb5Mu2XfBzv9gGvqvtmBUWIL5nts9FsgVr2V722TWzAPn/We1/7yUfCeG3qmp2BV30JBrw9zmS9PYLr3wZshYIaAGQJmCJghYIaAGZghYIaAGQJmCJghYIaAGQJmCJiBGQJmCJghYIaAGQJmCJghYIaAGZghYIaAGQJmCJghYIaAGQJmYAZmYIaAGQJmCJghYIaAGQJmCJiBGZiBGQJmCJghYIaAGQJmCJghYAZmYAZmCJihXdD/aIdljl+rzK0AAAAASUVORK5CYII=" alt="" />(手动队列)
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAcoAAAChCAIAAADIumimAAAABmJLR0QA/wD/AP+gvaeTAAAACXBIWXMAAA7EAAAOxAGVKw4bAAAWj0lEQVR4nO3db3AbZX4H8N/KspM0afCKlD9NDiytyUFKe9iJIJg/057GQ51j5m4YOy+YTNscjsLADCnD9WbuFdOZG0qnQAIv6KDjytxM+yZyIXcJ9oARHUqTYhRbXAnkYluW0wa4XILWyRknkbTavlhpvdp/2lX2sf7k+3nh0T5ePfvbZ3d/evbR7or74IMPyECWZeML5bX2hXZSNz80rIGBASIaGxurWvjFF19s27ZNnTx+/HihUDh+/Pj27dtDodCKBAvQxPw+n89YqqZOjuPUSY7jdNlTNwM0hbGxsYGBgYGBATWZmuZWIpJluVgs6iaLxaLuMxUATPmV/KilJk11kgy5VdeBJUM3FhrZ6Ojojh07BgYGlBdKiXHzKclUN6nLuVqzs7PsYm4W3d3dygu0Bl3zrWHSezV2XU1Tp+lYAVXmXGhYR44cefjhh5XceuTIEdOMKUlSoVDQTirpVZIk4/adnp7u7e3t6upiGXWjm5+fn5qa2rx58/T09ObNm+sdTv2dOnXqWm4Nu/RKmq6r7iSRNGnXOBpLSK9Nxao3akyvSoZVXmjnnJ6e7unp2bhxYz6fZxtrY9u4cWOhUEilUps3b5Ykae3atfWOqM4EQTh58uQ12xrcxMSErkjbV1WzpzrippwhfvrppyseKnjp9ddfJ6Lh4WH1hXGebDa7adMmdfLMmTPFYvHMmTO33HLLjTfeqJ3z7NmzmzZt4nmecdRNQBTFM2fOKO3T0dFR73DqLJfLnT179pptDS6ZTGqnjcOpWkpulSTpxIkT+/btq0/IAADNwOSrLSva833n7wIAuDbpx151vddisagOvHIcp2ZVpFcAAHtV0itpLiHgygjpFQCgGrvBAW1iJaRUAAA37HqvpLmKQBkl8Pl8ygukWgAAe5bpVZZlJZkSkZJYqdyfRXoFAKjKb3phFlVelaXeCqkoFApff/11PaIFAGgaftPbCqiyG0vlqwjUJGv6IBit//n0M1EUnUTQ2dn5p3duqVohAEBz8d9///3aaZusqtxsrvRez507Z1/vbDpzazBEZLw1tjSu8MVvvyZZJqIvz85s2njz9ddf79UqAQA0An8wGNROaxOr9k4t5YVyE7rCvl4+wN95R7fNgwe2fLubiDiOPjz60ZUrVzxYldpkErHJwNBgj8XtnGJqJJ7dGo0EdeWZRGwuZCy2Y1XViql7AKxZrKCYGomnBettzGShAKZfbenSq1qu/PX5fE6+2vL7uPnTvzv04QznkzmfzLXJvjZ54DvdN924fnHxGyJau27tv/9XhoiCf2hagZgaiSez5alAuHx0WKXDTCI2nlZeCv0ts7NnErFxWl4dXaJgmzc8Y9hkmURsXAwvl2QSsfG00B8NzbkpF4S0aPPBWGNsuh1vJXYmRu3TOkdB8/I5pKRU7aR9vbIsc1zb/IXF+d8v/u+li/935cKZ/EI+L5Fc8XCmtg7zZzUphP5oyfK+F+wNU3q+clQ3k4jFxkmdOTQ3knI07Nv4giGBxIXyyojz6Sxll9d+IZsNCF2NnVvJZJMFI/1CNpkobSQxNZkOhIciQZflEZM9wRTfMxi1ysJmu5N2x+un8VgskXG9zm4wah/k1vrzzRjMzs6qLxTpdDqdTs/NzaXTaYfp9UouT0R/tGEV15G/kL947vLXv730OyIi4mQimWQiWs1f/oMN37iNmO8SKnfGTEL3UR2MNHp/zrnOQGA5ny5ks4IgZLMLyqS4IDZDdjXZZKWEMJUhElOJJIUjpQ3mqtxYrSexVQhGokNhcZxtgmXUPlB3/kcffVQ7bfqILPVBWbOzsx9//HEwGDx//ryT2j8/e2ZJWvKvkto6Cm2cMlwrE8kccUS0ll/0+/P0++scRbp8JtwlUHwq01PKp5m5dCA8ZP5RrRkxqDjL05YTBQLG+QNh/dla2lCL86UEwkODPbp1SWaF/mgkqDkXNaub7xICyewCEU+UmUsLoaGAGJ/LRIJBEufTWX4rr1+Wph5lWLCfxsfTgfDQYJezADTv0oVlHqux0Qwluk1GpCSE2PiIGMhSeEiTDNyUm1RLJhtreXQ0k4hNBsJ8Mpm2jc1kEyhN7mIP0Q7JVgzPqnMGwmE+mQ4MDfbwjNqngj5yMTUST/JKsJoxKKsVhFr4Xc0dDAYLhUIymbzhhhuczH+ZvmlfU2jrkNraC/4O5UHLnJJbiej2DbcQ0ZdfWWbq9HhseUt3qcV8z1YhVt7frZVGsKLqmG0s0V86xsapPxpVd3ZRnX8yMBSN8KQcEInO0gGRHp/rj0YjpbkTld9o2S1luZyISNS9Y5BX+hp8f3TQek2WD+7MXFoIRfjOhUB6QSTiF7JZIRTU1qiPoTJ4EucdB2C2ymJqiiLRKF9RaFxN02Y022RKQhANycBFuUm1thuLiLLJ7NZoNKKEluoa7OEd7k5Wq+Zkodoa1H1PTI3EiQJWK+JF+9hG3jPYn41NpnqDnVPjYnhoMGizglAbd+lV5fCuLf+avL+90NZeaGsv+NvzVB4WUHTzISL6kizTa2V3jh+MlnuAwZAwXu2AUHq12jHbQHwuEwlSRW83GBJosjw/ZdPxmHqXRaA85in0l6NQK1EXbL8U444+l4ilaTmd8Z08Jcdjok1Hge8SAukFkcQFMRDoVLpsiXmxZ2EuHQj02sUQrAzeTQBmq8z3RHgxNRIr919NFm3ZjLzJJsskxkVBoKSS5Ki2ckO1JpF3atc/EO4Nqs1qVYlBINDpcg/pNKum4kyL79kqJCfL/2LUPupyzTZKMNI/F4vHKBAeivDWs1m2ClTDNr22r8q1dRT8/oK/Pd/mLxDR8qVaMuULhUK+ygVeFoIhYXwy1RvsUY7byXmxx8GT8gOBTqIFm/8bs1wNI3t2S0mLYoBIs9MGI6WuVCyWtTgb4zv57NyCSGkSIrxmWgwIvVbrHAiYHt61BaAQUyPxJIWHolFeOdu1Wn+Ls0rNJiNSkkF4aLCHAuVeJNVUrqu2NraVZKaSJAzxRAte7SFOYvCqfcocnupjRMBTvr36X192pHp65bgrVy7dvUHY1nlb7/rNd6294ztr/uTKlUvq/2VZLkqSZPErTybE1Ehs+YoAzbetwd4wJeOai*ZGUSMGQ5tvU0kHSxZNSPpUpVzqp6cIsl1MmsfxtRnpOnTuRLJ+Qa99VbSmZVHkGYevg4JCQjpe/jBZTqQwR8T2DQ+GA+p2VTjAkpOemslT+Gstk2jQGMw4DMFnlhWw2UPrKRJxPZ00aLZMqN7tpM2o2mZgaGU8LW3t4Ir4nEqZy9G7LddVaRO6A+QUEVB5IUVbb9R5SuubDork0+x6j9lEPGYvIlZQ8pM5vvYJQG1a912JRvuPb3+r6Fq8MBnA+P1GRZNnf3rFu3bqCJElSUSpKPl+tj4YpnyPzPPE9g9HOREw9qRH6oxGeiI9E+ytLlY9lZYwqVv56QaDSTh6MDIVH4rGYWkd5UQLNxWLjanHlARu0XMpybUpl5YO3FG4sRkJ/NNI5panbIhcEQ8L4eFoIRaymLWKwarrqAZiscrA3PBlXlhEQhPK3gcbV5K2acXlYYyqezAr96vhETyScjscTnf007qq8tCk0e4J55E5UVqIO+lMgXBqK1K9stT2kFGUsadlc2n2PTfv0qlWbRF4aNY/wPC23p+W2g5qo2S06Kr9Ge7kdsXLB8OHcqw/prhyQJGlmZiaZTHZ0dOzdu9em3jcPHVl/3XpjuXJdV1GSiuVhgmw2++B922+66Sa3oeN2GTYYtiujqj2ptg67k+F+AuzSLcYfHZVfGyAimn35vtti1Ld/+sOnBHnm5QdesHtb1d7rwEORCxcuWP3Cs5bP57vuOmfXZlVy/o0vNAhGm8yTaldkdxJTI1Odg+UrtMbTgXDF8Dl26RbDqel1TOm69u0/9eFTgsV1r5Ik5fP5eDy+evXqPXv21Dv41lN5QW597u9FF4olzbXD+Bqp5XHDh/P//JdERDT7yoN3PPPf5X9s/6cT7z8Z0j4oS02vb7311po1a4aHh+sWNQBAw/PJpbQpScEn/+Py5UuXLh36IRHRRyOjM5qsqs2whN/dAgCoxvfZqWklaY498eevTEuSJEWe+sd7iGhL6FbJhPrzMPWOHACgofk/+vGfrf0xEe3evfujN5SXRBR+7viL35UkSX3Mq3YElpBeAQCq8Wt+suWll17SPNJFSa7lb7cwOAAA4Ipf97sD2sdlEZHxygGkVwAAJ/xKulTZpFf0XgEAnLNMr1T+HUNjhiWkVwCAatylV/ReAQAc8udyOe20Mb2qtxWovxRLRNPT08iwAAA2fNVnMbjrrrs2bdrkeSgAAK2klvQKAABV+ScmJrTT6rCAbnxAHSVQnDt3rj7xAgA0CU5e/nkWomq/FKs80iWXy01MTOzcubNeQQMAND4MDgAAMIH0CgDABNIrAAATSK8AAEwgvQIAMIH0CgDABNIrAAATvr1cyd6xctnsKw/4/e3t7R0dHU++o8757tM8v2HDhptvvvmRf5mvR6gAAE1lVLl/YDRKFB2V5WJxev+e/b8pFPL5fO7wMNFjh5aWFhff3E109z9Mnj9//quvvjp9+vTBg8/VO3AAgMZWvj9r5kAfRUdLv6z1m5fuLf//sUNLS4tv/pDueX5SFJfT63N/Vc+gAQAanmHsdfblB9radtMb+Xw+d/LF7fWICQCgFSz3XZXBgbej1FcaHDj54r3awYG/iSu913979tkPMDgAAOBQdLT0DJfp/X2lonuHh7eX0uvixU+ev7tUvOsXp08fPHiwXoECADQFPDELAIAJXPcKAMCEv+Z36rq9hN83ZExt8KrtrNs0zreL8kZ1frf1WM2vq/YaUa+1bpzW1u4PDuOx2cllWdYV1lD/Cqu996quj3JXApkl3NZTx3V0tYOWbxZxsV1Mc6vzemzmb+Hdo14r1fiNqd0fyFnAurcY/3WV9a+82nuv16DG3IQ2nAds3+Vxu+KmZzbKaH5j9jJqY98s7Na0Xssl296lJzU7SaxNxPv0qt0ANieb2nZkXe5JnGqhaafM6rWxfpszbifr5Ryj3GrVya26XHYZ1mZ7mU662n+qbl9jxqmhftP57VfW4XJtBvGYnlx7VaF959TV7rTygwkefLWlHDNUjtjq88eqM8+63IrbOHWDIVU3j/3ncM3r5Yq3u7j2ta6tGC3XCfvtZYzT8/3HuD+Ybiz7+tktV/su0zZxuFyrhVblaixYLnMSiav66zKY4EF6tWrxGvopxnqMbW16kNiUV2Uap8NtXHP9NjN7slwPgzcW6pqaxXLdMm03+zhtQq3tw6wZebifW9VPbj5unac/mzNOq5qppvxwNRiOvWo/MK+yEtNC45azOZzcxulh67tqB8+X63BOm9P2Gj4jTcvdbhdPFurV/K3KbTsYT+aqzsy6qTlOf/G+zZwrFpWisa57tfos1ZbrxiKqlrOOh4Wrr7+2dGPVAdSxaee65FbtUrTxVN0fvNq+rPcH1stlEb+u8XX1Ox8E8DAez/NDVbWnV21ec1Kua2jjST2jcrfx29Rj+umnnd84tmWs34qT9XKyZ2jnd5XUdJVb1aN9bSwxXS7T3GrVbk7iJJf7lVUT6dZOmziMrXf1reFqubp3GStxu5O4HXm7yv3faqXcxu9h+zvnv4/jjlHfgZmj+7rdvdMqPpu43b7Fq3K3M7v9lzEF21RiOnPNb3EepBNO4rGZx5PtUgPWcbrdZK7qd7tx3S63hnbwhH3lNcfvfBFXP//V8x0jio66zq0AAGDPR30H/m6g3lEAALQc34FfoOcKAOA9H5IrAAALvpdn6x0CAEAr8v3tXyPBAgB4z0fHakywsoHnwTWUa2Q1nUNrANjz9VGNCVZ7gedK3ghRLytz0VyjtWGjxQPQRPxHcfw0jEbLZU5uDwMAK035vNeqi7ZaqGn9VrcYOlmWsdtec/3aO/9sVqHmdrAqt2oft/HY12PaCG7XC6C5NN/zXm1ob4g2Hu0ejmCYpoyrrF832GJMTw7rr609jeVW8WhnNl2Lq4wToGV40Hu1OtJkWeYMzwozHkWc5ml4umPYtNzGyhyipv3QxswOjd8lbMx2A/DESj/v1eapDca05eq03eps3XOc2dNRGz+RNSa0G7Sw+jzv1fQhY8aTWdYZU63Z7cCrVUi6a5Vqrt+ra54arR7n9ctl7BYKwFrzPe/VinZ+t8O1VWezqc0+Tuf1k0Vv/Wra4WrqsYqHLD4dncRjrLCGzx6AZlH74IDNlxtevcXtIWd6tl71FN5V2rJflilX6cNm8MQ5V+1pvyLO47Gpx+pfNewqAE2E4dhrgzOexTdX/QDQ4K7d9Mo65SGlAlzjGuunDAEAWoZP+e5l71i9AwEAaC0+WZZleWbLT5FgAQC8pIy9du87+lqdAwEAaC3Gsdexx9va/H5/e3t7R8cT7yhl6Vf71+97T3md+dkjt/4ET+AGALDnqxx3HXvc973P9p8qFAr5fD53mL6/+sl36xccAEDz8s0cOLFD/W5r7FCsb/8bT5V/3fChZ17Y/vPDyK8AAO75uvcdleXRaGyHxXdb22/HT8kCALinjr32bbmNaOAH0WNP736lPLL6zos/osGBkDLx+ewcEVHmvV9NrniUAADNKjpaekBRsfj2nuXi4V9evry0tLS4uPjJ8/coRdt27dpKjz538GB9AgUAaBImj7vWKmpIkiRJUj6fz+VyExMTO3furFfQAACNDzfFAgAwgfQKAMAE0isAABNIrwAATCC9AgAw4eJx2hcvXlSuHMjn81euXGEXEwBAC0DvFQCACf+vfz2vnU4mPx8a+q5y0eu6de11igoAoOn5Q6E/1k7LshyPvz84+Bf1CggAoDWYDA7cffeWePz9lQ8FAKCV6NPr8eMnP/74cyIaGUGGBQConf7KgZ07I8rAazyeqEtAAACtAVcOAAAwUUN6/c+/v3NXMp30PhYAgBZSW+/1k8Qxj+MAAGgxtaXXuyIPhz0OBACgtWDsFQCACaRXAAAmkF4BAJioIb0++OyJfw3z3ocCANBK0HsFAGAC6RUAgAn/wYMVN78qv8ut+3VuAABwy//YYwPaablSvcICAGh2GBwAAGDCxW9trV+/XvmtrVwut2rVKnYxAQC0APReAQCYQHoFAGAC6RUAgAmkVwAAJpBeAQCYQHoFAGAC6RUAgAmkVwAAJpBeAQCYQHoFAGAC6RUAgAmkVwAAJpBeAQCYQHoFAGAC6RUAgAmkVwAAJpBeAQCYQHoFAGAC6RUAgAmkVwAAJpBeAQCYQHoFAGAC6RUAgAmkVwAAJnwcx3Ect3es3oEAALQWnyzLsjyz5adIsAAAXvITEVH3vqOv1TkQAIDWYhx7HXu8rc3v97e3t3d0PPGOUpZ+tX/9vveU15mfPXLrT2ZXMEQAgGbkqxx3HXvc973P9p8qFAr5fD53mL6/+sl36xccAEDz8s0cOLFD/W5r7FCsb/8bT3WX/vnQMy9s//lh5FcAAPd83fuOyvJoNLbD4rut7bd3m5YDAIAddey1b8ttRAM/iB57evcr5ZHVd178EQ0OhJSJz2fniIgy7/1qcsWjBABoVtFRWVEsvr1nuXj4l5cvLy0tLS4ufvL8PUrRtl27ttKjzx08WJ9AAQCaBCfLsnZarlTUkCRJkqR8Pp/L5SYmJnbu3FmvoAEAGh9uigUAYALpFQCACaRXAAAmkF4BAJj4fzCCpL2WmCNNAAAAAElFTkSuQmCC" alt="" />(STL自带)
一直超时找不到原因,改成手动队列跑得飞快,还有就是 string 类型也要谨慎使用,这些STL自带功能会消耗时间
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;
const int N = ;
int n,m,MAX;
char mp[N][N];
bool flag[N][N];
bool vis[N][N];
int dir[][] = {{,},{-,},{,-},{,}};
struct Node{
int x,y;
};
char res[N],ans[N],ans1[N];
bool check(int x,int y){
if(x<||x>n||y<||y>m||mp[x][y]=='#') return false;
return true;
}
Node q[N * N];
int bfs(int x,int y){
memset(flag,,sizeof(flag));
int head = , tail = ,ret = ;;
q[tail].x = x; ///手动队列非常快
q[tail++].y = y;
flag[x][y] = true;
while(head!= tail){
int nowx = q[head].x;
int nowy = q[head++].y;
for(int i=;i<;i++){
int nextx = nowx+dir[i][];
int nexty = nowy+dir[i][];
if(!check(nextx,nexty)||flag[nextx][nexty]||vis[nextx][nexty]) continue;
ret++;
flag[nextx][nexty] = true;
q[tail].x = nextx;
q[tail++].y = nexty;
}
}
return ret;
} void dfs(int x,int y,int step){
if(step>MAX||step==MAX&&strcmp(ans,res)>){
MAX = step;
strcpy(res,ans);
}
int GO = bfs(x,y); ///预处理最好的情况,所有点都可达
strcpy(ans1,ans);
ans1[step] = '';
if(GO+step<MAX||GO+step==MAX&&strcmp(ans1,res)<) return; ///剪枝,(x,y)能够走的距离 < 答案
for(int i=0;i<4;i++){
int nextx = x+dir[i][0];
int nexty = y+dir[i][];
if(!check(nextx,nexty)||vis[nextx][nexty]) continue;
vis[nextx][nexty] = true;
ans[step] = mp[nextx][nexty];
dfs(nextx,nexty,step+);
ans[step] = ;
vis[nextx][nexty] = false;
}
}
int main()
{
freopen("f.in","r",stdin);
freopen("f.txt","w",stdout);
while(scanf("%d%d",&n,&m)!=EOF,n+m){
int tot = ;
for(int i=;i<=n;i++){
scanf("%s",mp[i]+);
for(int j=;j<=m;j++){
if(mp[i][j]!='#') tot++;
}
}
memset(res,,sizeof(res));
MAX = -;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(mp[i][j]=='#'||MAX==tot&&mp[i][j]<res[]) continue;
memset(vis,false,sizeof(vis));
ans[] = mp[i][j];
vis[i][j] = true;
dfs(i,j,);
}
}
printf("%s\n",res);
}
return ;
}
/**
5 6
245356
342534
534635
423535
324345
*/