简答题 偏难
#7192

夺宝探险 你无意中发现了装满了宝藏的迷宫,你想要获得尽可能多的宝藏,但是迷宫里的机关阻碍了你的计划。迷宫的地面是M行N列的矩形网格,每格是一块带有机关且放置了1…

夺宝探险

你无意中发现了装满了宝藏的迷宫,你想要获得尽可能多的宝藏,但是迷宫里的机关阻碍了你的计划。迷宫的地面是M行N列的矩形网格,每格是一块带有机关且放置了1个宝藏的地砖,宝藏一共有K种,用1-K表示其种类,迷宫的入口只有一个,为迷宫的第一行第一列。地砖的机关如下:

1. 每次你只能踏到你与你所在地砖相邻的地砖上(即前后左右4块);

2. 当你踏上某块地砖后,其上的宝藏(假设种类为k)自动归属你,同时所有放置了种类为k的宝藏的地砖碎裂,你无法踏上,你当前所在的地砖在你离开后也会立刻碎裂;

3. 当你无路可走的时候,你会被传送回迷宫出口,无法再进入迷宫。

你想知道你最多能获得多少宝藏。

时间限制:1000

内存限制:65536

输入

输入的第一行是三个用空格隔开的整数,分别是M、N和K(1 <= M,N <= 20, 1 <= K <= 100) 之后是M行,每行包含N个范围为1-K的整数,用空格隔开,表示放置的宝藏种类

输出

只有一行,为一个整数,表示最多能获得的宝藏个数。

样例输入

3 4 5
1 2 3 3
2 1 4 3
1 5 1 2

样例输出

4
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; using namespace std; int m, n, k; int a[22][22]; bool jewel[101]; int have = 0; // 获得的宝石数 int ans = 0; int dirx[4] = {0, 0, 1, -1}; int diry[4] = {1, -1, 0, 0}; void dfs(int x, int y) {   for (int i = 0; i &lt; 4; i++) {     int nx = x + dirx[i];     int ny = y + diry[i];     if (!jewel[a[nx][ny]]) {       jewel[a[nx][ny]] = true;       have++;       dfs(nx, ny);       have--;       jewel[a[nx][ny]] = false;     }   }   ans = max(ans, have); } int main() {   cin &gt;&gt; m &gt;&gt; n &gt;&gt; k;   int i, j;   for (i = 1; i &lt;= m; i++)     for (j = 1; j &lt;= n; j++)       cin &gt;&gt; a[i][j];   jewel[a[1][1]] = true;   jewel[0] = true;   have = 1;   dfs(1, 1);   cout &lt;&lt; ans;   return 0; }</pre>
这道题暂未补解析。