本人第一篇正式題解!
本題的主要思路:
①求挖地雷的最多個數。
②輸出最多地雷的挖掘方法。
明确思路後代碼實作
資料範圍 n<=20 是以我們完全可以跑n遍DFS 求出其中的可以一次性挖的最多地雷數, 然後再跑一遍 計路DFS 把一個等于這個最多地雷數挖法記錄下來輸出,本題就結束了,簡單易懂的雙DFS。
下面是AC代碼:
#include<bits/stdc++.h>
using namespace std;
const int INF=2147483647;
int n,a[21];
int f[21][21],step=0;// f[i][j]用來判斷i和j是否聯通。 step用來記錄最多的地雷數
void read(int &x)
{
x=0;int p=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') p=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
x*=p;
}// (讀入優化自動忽略)
void dfs(int x,int y)// 求最多地雷數的DFS x來記錄目前到達的點,y來記錄地雷數目。
{
bool p=0;
for(int i=1;i<=n;i++)
{
if(f[x][i])
{
p=1;
break;
}
}// 判斷n個地窖裡是否有地窖與目前地窖x聯通。
if(p==0)
{
step=max(y,step);
return ;
}// 沒有地窖聯通,已經挖到頭了,判斷已挖到的地雷是否為最大地雷數。
for(int i=1;i<=n;i++)
{
if(f[x][i]) dfs(i,y+a[i]);// 如果聯通就挖下去。
}
}
int e1[21];// e1數組用來記錄挖掘順序。
bool p=0;
int dfs1(int x,int y,int z)// 記錄挖掘順序的DFS x,y所代表的意義同上,z來記錄已經挖了幾個地窖。
{
if(y==step)
{
p=1;
for(int i=0;i<z;i++)
cout<<e1[i]<<" ";
return 0;
}// 如果為最大地雷數,輸出所記錄的順序然後直接跳出就好了!
for(int i=1;i<=n;i++)
{
if(f[x][i])
{
e1[z]=i;
dfs1(i,y+a[i],z+1);
}
}
}
int main()
{
read(n);
for(int i=1;i<=n;i++)
{
read(a[i]);
}
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
int y;
read(y);
if(y) f[i][j]=1;
}
}
for(int i=1;i<=n;i++)
{
dfs(i,a[i]);
}
for(int i=1;i<=n;i++)
{
e1[0]=i;
dfs1(i,a[i],1);
if(p) break;// 已經找到最優順序,直接Break掉!
}
cout<<endl<<step;// 換行輸出最多地雷數!
return 0;
}// AC!!!