**
Problem I: 挖寶游戲
前言：第一個博客，有點粗糙，，，
**
Description
華為采用鴻蒙系統后，為了回饋所有支持華為的用戶，特別設定了一個挖寶游戲，挖寶游戲很簡單，在一個N*M(左上角坐標為1,1）的地圖上，埋著一些寶物，用戶只要在K步內能挖到寶物，游戲就結束，然后華為給用戶反饋紅包，紅包的多少跟步數有關，步數越少，紅包越大，紅包錢數有一個計算公式：（K-s+1）*10
s為你挖到寶物的步數
走的時候只能上下左右四個方向
Input
第一行 2個整數分別為N和M
第二行 2個整數分別為你的坐標X和Y
第三行一個整數為K
然后是一個N*M的矩陣，每行由M個整陣列成，整數為0,1，-1，其中0代表空地，1代表寶物，-1代表陷阱不能走上去
Output
輸出3個整數，分別為s,紅包錢數，如果你不幸一開始掉在陷阱輸出Die,如果找不到則輸出0
Sample Input
【輸入樣例1】
2 2
1 1
1
0 1
1 -1
【輸入樣例2】
2 2
2 2
1
0 1
1 -1
【輸入樣例3】
2 2
1 1
10
0 -1
-1 1
Sample Output
【樣例輸出1】
1 10
【樣例輸出2】
Die
【樣例輸出3】
0
HINT
提示：可能有多個寶物，假設你已經知道了地圖，可以以最優方式去找
N M<=20
下面是代碼，
#include<bits/stdc++.h>
using namespace std;
int a[1000][1000],b[1000][1000];//b記錄一開始的坐標x，y到每個不是陷阱的點的距離，
int main()
{
int n,m;
int mins;
int i,j,k;
int x,y;
int s=0;
cin>>n>>m;
cin>>x>>y;
cin>>k;
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
cin>>a[i][j];
if(a[i][j]==-1)b[i][j]=-1;//b為-1代表不可走
}
}
if(a[x][y]==1)
{
cout<<s<<" "<<(k-s+1)*10<<endl;
}
else if(a[x][y]==-1)cout<<"Die"<<endl;
else
{
int flag=0;
s=1;
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
if(abs(x-i)+abs(y-j)==1)//1步到達的范圍
{
if(a[i][j]==1)
{
flag=1;
cout<<s<<" "<<(k-s+1)*10<<endl;
goto lap;
}
else if(a[i][j]==0)
{
b[i][j]=1;
}
}
}
}
for(s=2; s<=k; s++)//走s步擴散到的范圍
{
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
if(b[i][j]==s-1)
{
if(i-1>=1&&b[i-1][j]==0)//向上走
{
b[i-1][j]=s;
}
if(i+1<=n&&b[i+1][j]==0)//向下走
{
b[i+1][j]=s;
}
if(j-1>=1&&b[i][j-1]==0)//向左走
{
b[i][j-1]=s;
}
if(j+1<=m&&b[i][j+1]==0)//向右走
{
b[i][j+1]=s;
}
}
}
}
}
mins=9999999;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(a[i][j]==1&&b[i][j]<mins&&b[i][j]!=0)//尋找滿足條件的最小距離，
{
mins=b[i][j];
}
}
}
if(mins<9999999)
{
flag=1;
cout<<mins<<" "<<(k-mins+1)*10<<endl;
}
lap:
if(flag==0)cout<<"0"<<endl;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/248516.html
標籤：其他