NC200446. 洛克王国之域外大逃杀
描述
输入描述
第一行三个整数，n,m, atk（n,m代表地图大小，地图外为死亡深渊，入者即死, atk为洛克的攻击力）（4<= n,m<= 1000）
接下来n行m列的图，‘.’代表空地，‘∗’表示魔物，‘#’表示宠物，‘L’为洛克。
接下来一行为魔物的攻击力，以最左上方的魔物为第一个，最右下角的魔物为最后一个，以从左到右，从上到下的顺序给出。
再接下来一行为宠物的攻击力，给出顺序与魔物相同。
其中宠物的数量 ≤2, 魔物的数量 ≤20，所有攻击值数据在int范围内。
输出描述
逃亡的最短时间，如果无法汇合，输出“you die!”。
示例1
输入:
4 4 3 ..#. .L.* .... .#*. 2 3 1 7
输出:
6
说明:
第一个魔物的坐标为(2,4)，攻击力为2，第二个魔物的坐标为(4,3)，攻击力为3。示例2
输入:
4 4 4 ...# .L.. ..*. *..# 2 4 1 5
输出:
6
C++14(g++5.4) 解法, 执行用时: 390ms, 内存消耗: 18048K, 提交时间: 2019-12-14 21:24:49
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 50;
int INF = 1e8;
char mp[maxn][maxn];
int n, m;
struct st
{
int x, y, atk;
int t, num;
} am[maxn], ac[maxn];
int cntm, cntc;
int sx, sy;
int id[maxn][maxn];
int dis[5][maxn][maxn];
int matk[maxn][maxn];
int tx[] = {0, -1, 0, 1};
int ty[] = {1, 0, -1, 0};
queue<st> quec, quem;
int ans = INF;
int res = 0;
void bfs(int atk){
quec.push({sx, sy, atk, 1, 0});
for(int i = 1; i <= cntm; i++){
quem.push(am[i]);
}
for(int i = 0; i <= 2; i++){
for(int j = 1; j <= n; j++){
for(int k = 1; k <= m; k++){
dis[i][j][k] = INF;
}
}
}
dis[0][sx][sy] = 0;
for(int t = 1; ; t++){
int flag = 0;
while(quem.size() && quem.front().t == t){
st tmp = quem.front();
quem.pop();
int x = tmp.x, y = tmp.y;
for(int i = 0; i < 4; i++){
int nx = x + tx[i], ny = y + ty[i];
if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && tmp.atk > matk[nx][ny]){
matk[nx][ny] = tmp.atk;
quem.push({nx, ny, tmp.atk, t + 2, 0});
}
}
}
//printf("%d\n", quec.front().t);
while(quec.size() && quec.front().t == t){
//printf("999\n");
flag = 1;
st tmp = quec.front();
quec.pop();
int x = tmp.x, y = tmp.y;
//printf("x = %d y = %d num = %d dis = %d atk = %d\n", x, y, tmp.num, dis[tmp.num][x][y], atk);
for(int i = 0; i < 4; i++){
int nx = x + tx[i], ny = y + ty[i];
if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && tmp.atk > matk[nx][ny] && dis[tmp.num][nx][ny] > dis[tmp.num][x][y] + 1){
dis[tmp.num][nx][ny] = dis[tmp.num][x][y] + 1;
int num = tmp.num;
atk = tmp.atk;
if(id[nx][ny]){
num ^= (1 << (id[nx][ny] - 1));
atk += ac[id[nx][ny]].atk;
//printf("id = %d atk = %d\n", id[nx][ny], ac[id[nx][ny]].atk);
}
dis[num][nx][ny] = dis[tmp.num][x][y] + 1;
if(num == res) ans = min(ans, dis[num][nx][ny]);
quec.push({nx, ny, atk, t + 1, num});
}
}
}
if(flag == 0) break;
}
}
int main()
{
int atk;
scanf("%d%d%d", &n, &m, &atk);
for(int i = 1; i <= n; i++){
scanf("%s", mp[i] + 1);
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(mp[i][j] == 'L'){
sx = i, sy = j;
}
if(mp[i][j] == '#'){
ac[++cntc] = {i, j, 0, 1, 0};
id[i][j] = cntc;
res ^= (1 << (cntc - 1));
}
if(mp[i][j] == '*'){
am[++cntm] = {i, j, 0, 2, 0};
}
}
}
for(int i = 1; i <= cntm; i++){
scanf("%d", &am[i].atk);
matk[am[i].x][am[i].y] = am[i].atk;
}
for(int i = 1; i <= cntc; i++){
scanf("%d", &ac[i].atk);
//printf("ac[%d] = %d\n", i, ac[i].atk);
}
//printf("res = %d\n",res );
if(cntc == 0){
printf("0\n");
} else {
bfs(atk);
if(ans == INF){
printf("you die!\n");
} else {
printf("%d\n", ans);
}
}
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 78ms, 内存消耗: 12040K, 提交时间: 2022-08-10 14:23:45
#include<bits/stdc++.h>
using namespace std;
struct node1
{
int x,y,atk;
}monster[25];
struct node2
{
int x,y,atk;
}pet[2];
struct node3
{
int x,y,h;
}Q[1000005];
int n,m,atk,L1=0,L2=0,dx[]={0,0,1,-1},dy[]={1,-1,0,0};
char R[1005][1005];
bool V[1005][1005];
int BFS(int sx,int sy,int ex,int ey,long long atk,int preh)
{
int i,j,d,r=1,f=0,x,y,h,X,Y;
memset(V,0,sizeof(V));
V[sx][sy]=1,Q[0].x=sx,Q[0].y=sy,Q[0].h=preh;
while(r!=f)
{
x=Q[f].x,y=Q[f].y,h=Q[f++].h;
if(x==ex&&y==ey)return h;
for(i=0;i<4;i++)
{
X=x+dx[i],Y=y+dy[i];
if(X<0||X>=n||Y<0||Y>=m||V[X][Y])continue;
for(j=0;j<L1;j++)
{
d=abs(X-monster[j].x)+abs(Y-monster[j].y);
if(h+1>=d*2&&atk<=monster[j].atk)break;
}
if(j<L1)continue;
V[X][Y]=1,Q[r].x=X,Q[r].y=Y,Q[r++].h=h+1;
}
}
return -1;
}
int main()
{
int i,j,a,b,ans1,ans2,sx,sy;
scanf("%d%d%d",&n,&m,&atk);
for(i=0;i<n;i++)scanf("%s",R[i]);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
if(R[i][j]=='L')sx=i,sy=j;
if(R[i][j]=='*')monster[L1].x=i,monster[L1++].y=j;
if(R[i][j]=='#')pet[L2].x=i,pet[L2++].y=j;
}
for(i=0;i<L1;i++)scanf("%d",&monster[i].atk);
for(i=0;i<L2;i++)scanf("%d",&pet[i].atk);
if(!L2){printf("0\n");return 0;}
if(L2==1)
{
a=BFS(sx,sy,pet[0].x,pet[0].y,atk,0);
if(a!=-1)printf("%d\n",a);
else printf("you die!\n");
return 0;
}
a=BFS(sx,sy,pet[0].x,pet[0].y,atk,0);
if(a!=-1)b=BFS(pet[0].x,pet[0].y,pet[1].x,pet[1].y,(long long)atk+pet[0].atk,a);
if(a==-1||b==-1)ans1=-1;
else ans1=b;
a=BFS(sx,sy,pet[1].x,pet[1].y,atk,0);
if(a!=-1)b=BFS(pet[1].x,pet[1].y,pet[0].x,pet[0].y,(long long)atk+pet[1].atk,a);
if(a==-1||b==-1)ans2=-1;
else ans2=b;
if(ans1!=-1&&ans2!=-1)printf("%d\n",min(ans1,ans2));
else if(ans1==-1&&ans2!=-1)printf("%d\n",ans2);
else if(ans1!=-1&&ans2==-1)printf("%d\n",ans1);
else printf("you die!\n");
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 301ms, 内存消耗: 18580K, 提交时间: 2019-12-19 17:02:41
#include <bits/stdc++.h>
using namespace std;
using pi = pair <int, int>;
const int N = 1e3 + 10;
const int d[N][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
char a[N][N];
struct node
{
int x, y, z, s, w;
node(int X = 0, int Y = 0, int Z = 0, int S = 0, int W = 0) : x(X), y(Y), z(Z), s(S), w(W)
{
}
};
int f[N][N][4];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
node s;
int n, m;
cin >> n >> m >> s.z;
vector <node> b, c;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
{
cin >> a[i][j];
if (a[i][j] == '*')
{
b.emplace_back(node(i, j));
}
else if (a[i][j] == '#')
{
c.emplace_back(node(i, j));
}
else if (a[i][j] == 'L')
{
s.x = i;
s.y = j;
}
}
for (int i = 0; i < b.size(); ++i)
cin >> b[i].z;
for (int i = 0; i < c.size(); ++i)
cin >> c[i].z;
int fin = (1 << c.size()) - 1;
memset(f, 0x3f, sizeof(f));
f[s.x][s.y][0] = 0;
queue <node> q;
int ans = 0x3f3f3f3f;
for (q.emplace(s); !q.empty(); q.pop())
{
node u = q.front();
// cout << u.x << ' ' << u.y << ' ' << u.z << ' ' << u.s << ' ' << u.w << endl;
if (u.s == fin)
{
ans = min(ans, u.w);
break;
}
for (int i = 0; i < 4; ++i)
{
node v(u.x + d[i][0], u.y + d[i][1], u.z, u.s, u.w + 1);
if (v.x < 1 || v.x > n || v.y < 1 || v.y > m)
continue;
bool die = 0;
for (auto j : b)
if (v.w >= (abs(v.x - j.x) + abs(v.y - j.y)) * 2 && u.z <= j.z)
{
die = 1;
break;
}
if (die)
continue;
for (int j = 0; j < c.size(); ++j)
if (c[j].x == v.x && c[j].y == v.y && (v.s & (j + 1)) == 0)
{
v.z += c[j].z;
v.s |= (j + 1);
}
if (f[v.x][v.y][v.s] > v.w)
{
f[v.x][v.y][v.s] = v.w;
q.emplace(v);
}
}
}
if (ans == 0x3f3f3f3f)
cout << "you die!";
else
cout << ans;
}