Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"cycleck","updateTime":1531384579000,"title":" - Harry And Dig Machine ","dislikeCnt":3,"content":"```\n#include\u003ciostream\u003e\n#include\u003ccstdio\u003e\n#include\u003calgorithm\u003e\n#include\u003ccmath\u003e\n#include\u003ccstring\u003e\n#include\u003cstring\u003e \n#define INF 0x3f3f3f3f\nusing namespace std;\nstruct zb{ \n int x,y;\n}p[55]; //记录关键点\nint dis[55][55],dp[(1\u003c\u003c11)+15][50]; //dis用于记录关键点之间的最短距离,dp记录在第j个点的状态为i的总距离 \nint n,m; \nint main (){\n while(~scanf(\"%d%d\",\u0026n,\u0026m)){\n int num\u003d0; //记录关键点的个数 \n memset(dp,INF,sizeof(dp)); //初始化dp数组为无穷大 \n for(int i\u003d0;i\u003cn;i++){\n for(int j\u003d0;j\u003cm;j++){\n int a;\n scanf(\"%d\",\u0026a);\n if(a||(!i\u0026\u0026!j)){\n p[num].x\u003di;p[num].y\u003dj; \n num++;\n }\n }\n }\n for(int i\u003d0;i\u003cnum;i++){\n for(int j\u003di+1;j\u003cnum;j++){\n dis[i][j]\u003ddis[j][i]\u003dabs(p[i].x-p[j].x)+abs(p[i].y-p[j].y);\n dis[i][i]\u003d0; //计算每两个关键点之间的距离 \n }\n }\n dp[0][0]\u003d0; //在第一行的状态为0,所走距离为0 \n for(int i\u003d0;i\u003c(1\u003c\u003cnum);i++){ //枚举所有状态 \n for(int j\u003d0;j\u003cnum;j++){ //枚举关键点 \n if(dp[i][j]\u003d\u003dINF)continue;//是否已到达该点 \n for(int k\u003d0;k\u003c\u003dnum;k++){ //枚举目标点 \n if(i\u0026(1\u003c\u003ck))continue; //目标点已经过 \n dp[i|(1\u003c\u003ck)][k]\u003dmin(dp[i|(1\u003c\u003ck)][k],dp[i][j]+dis[j][k]);\n } //将该点所在位改为1,区该点遇上一点的较小值 \n }\n }\n int ans\u003dINF;\n for(int i\u003d0;i\u003cnum;i++)\n ans\u003dmin(ans,dp[(1\u003c\u003cnum)-1][i]+dis[i][0]);//取最小值为答案 \n printf(\"%d\\n\",ans);\n }\n return 0;\n}\n\n```","threadId":31395,"likeCnt":0,"createTime":1531384579000,"isWorkbook":false,"viewCnt":1785,"openness":2,"fav":false,"id":511,"trustable":false}