蒜头君得到一张藏宝图。藏宝图是一个 10 \times 1010×10 的方格地图，图上一共有 1010 个宝藏。有些方格地形太凶险，不能进入。
整个图只有一个地方可以出入，即是入口也是出口。蒜头君是一个贪心的人，他规划要获得所有宝藏以后才从出口离开。
藏宝图上从一个方格到相邻的上下左右的方格需要 11 天的时间，蒜头君从入口出发，找到所有宝藏以后，回到出口，最少需要多少天。
我在写这道题的时候不想太暴力然后问学长怎么做然后学长告诉我要状态压缩然后我去做了匡斌搜索专题里的奶牛踩白块的题因为里面有一个二进制枚举然后我找了一下午bug，很烦。。。最后发现这个并不能降低时间复杂度然后就又暴力了
#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;
int dp[11][11];
int vis[11];
int MIN = 1e9;
void DFS(int bian,int num,int step)
{
for(int i = 1; i <= 10; i++)
{
if(!vis[i])
{
vis[i] = 1;
DFS(i,num+1,step + dp[bian][i]);
vis[i] = 0;
}
}
if(num == 10)
{
step += dp[bian][0];
}
if(MIN > step && num == 10)
{
MIN = step;
// cout<<"bian="<<bian<<endl;
// cout<<"step="<<step<<endl;
}
}
int main()
{
dp[0][1] = dp[1][0] = 7;
dp[0][2] = dp[2][0] = 7;
dp[0][3] = dp[3][0] = 6;
dp[0][4] = dp[4][0] = 4;
dp[0][5] = dp[5][0] = 11;
dp[0][6] = dp[6][0] = 8;
dp[0][7] = dp[7][0] = 14;
dp[0][8] = dp[8][0] = 13;
dp[0][9] = dp[9][0] = 9;
dp[0][10] = dp[10][0] = 19;
dp[1][2] = dp[2][1] = 2;
dp[1][3] = dp[3][1] = 5;
dp[1][4] = dp[4][1] = 9;
dp[1][5] = dp[5][1] = 4;
dp[1][6] = dp[6][1] = 7;
dp[1][7] = dp[7][1] = 7;
dp[1][8] = dp[8][1] = 10;
dp[1][9] = dp[9][1] = 14;
dp[1][10] = dp[10][1] = 12;
dp[2][3] = dp[3][2] = 3;
dp[2][4] = dp[4][2] = 7;
dp[2][5] = dp[5][2] = 4;
dp[2][6] = dp[6][2] = 5;
dp[2][7] = dp[7][2] = 7;
dp[2][8] = dp[8][2] = 10;
dp[2][9] = dp[9][2] = 12;
dp[2][10] = dp[10][2] = 12;
dp[3][4] = dp[4][3] = 4;
dp[3][5] = dp[5][3] = 5;
dp[3][6] = dp[6][3] = 2;
dp[3][7] = dp[7][3] = 8;
dp[3][8] = dp[8][3] = 7;
dp[3][9] = dp[9][3] = 9;
dp[3][10] = dp[10][3] = 13;
dp[4][5] = dp[5][4] = 9;
dp[4][6] = dp[6][4] = 4;
dp[4][7] = dp[7][4] = 10;
dp[4][8] = dp[8][4] = 9;
dp[4][9] = dp[9][4] = 7;
dp[4][10] = dp[10][4] = 15;
dp[5][6] = dp[6][5] = 7;
dp[5][7] = dp[7][5] = 3;
dp[5][8] = dp[8][5] = 6;
dp[5][9] = dp[9][5] = 12;
dp[5][10] = dp[10][5] = 8;
dp[6][7] = dp[7][6] = 6;
dp[6][8] = dp[8][6] = 5;
dp[6][9] = dp[9][6] = 7;
dp[6][10] = dp[10][6] = 11;
dp[7][8] = dp[8][7] = 3;
dp[7][9] = dp[9][7] = 9;
dp[7][10] = dp[10][7] = 5;
dp[8][9] = dp[9][8] = 6;
dp[8][10] = dp[10][8] = 6;
dp[9][10] = dp[10][9] = 12;
memset(vis,0,sizeof(vis));
int step = 0;
DFS(0,0,0);
cout<<MIN<<endl;
return 0;
}
这题让我很难受很烦因为我比较菜最后写递归刚开始是错的因为我的step += dp[bian][i]刚开始直接写在了if里边然后就不对了因为虽然递归内层不会影响外层但这个step的改变是在外层本身改变的所以会错误
奶牛踩白块的题代码我给弄丢了有空再写一遍补上。
其实这个题我刚开始是想的能不能用最小生成树迪杰斯特拉神魔的图论部分的东西写但是这些我也忘了。。。而且学长还布置有任务所以先放在这下周再想想。