列表

详情

NC254925. 小红的战争棋盘

描述

小红正在玩一个战争棋盘。
棋盘可以视为一个 n 行 m 列的矩阵。小红初始往棋盘上投放了 k 支军队，每个军队属于不同势力。每回合，小红可以任选一个军队按“上、下、左、右”四种方向中的一种移动一个方格，会出现以下4种情况：
1.当这个军队移动到一个未被任何势力占领的格子，则军队移动成功，并将其占领。
2.当这个军队移动到自己势力的格子，此时军队移动成功。
3.若这个军队将移出地图的边界，将移动失败。该军队原地不动。
4.若这个军队将移动到另外一个势力的格子，那么两个势力将发生冲突，拥有较多领土的势力将获胜，并占领对方所有领土，消灭对方的军队。特殊的，若两个冲突的势力领土数量相等，那么势力名字的字典序较大者获胜。如果进攻方获胜，则进攻方移动成功。如果防守方获胜，那么防守方的军队保持原来的位置。
请你在每次移动操作后输出当前操作的结果。
ps：若投放军队的时候有两个或多个军队在同一格子，则直接发生冲突，名字字典序最大的那个势力存活，其他势力消亡。
对于字符串 a 和 b，我们认为满足以下两个条件中的一种时， a 的 字典序大于 b：
1. b 是 a 的一个前缀，且 a 和 b 不相等。
2. 对于 a 和 b中出现的第一个不同的字母，a 的那个字母的 ascii 值比 b 的那个字母更大。

输入描述

第一行输入三个正整数 n,m,k，分别代表棋盘的行数、列数，以及势力的数量。
接下来的 k 行，每行输入一个字符串 str，以及两个正整数x和y，代表每个势力的名字，以及初始的坐标为 (x,y)。保证初始投放的军队是没有重名的。
接下来的一行输入一个正整数 q，代表回合数。
接下来的 q 行，每行输入一个字符串 str 和一个字符 c ，代表即将行动的军队的势力名称，以及行动方向。c为 'W'代表该军队向上走，'S'代表向下走，'A'代表向左走，'D'代表向右走。
数据范围：




保证str是长度不超过10的、仅包含小写字母的字符串。保证 c 为'W'、'A'、'S'、'D'四种字符中的一种。

输出描述

对于每次操作，输出一行答案：
若本次移动占领了新的边界，则输出一行字符串"vanquish!"
若本次移动到了自己的领土，则输出一行字符串"peaceful."
若本次由于将移出边界导致移动失败，则输出一行字符串"out of bounds!"
若本次移动发生了冲突，胜利者是xxx，则输出一行字符串"xxx wins!"（xxx为势力名字）
若输入了不存在的势力，或者输入的字符串代表的势力已经败北，则输出一行字符串"unexisted empire."

示例1

输入: 

3 3 2
ranko 1 1
kotori 2 2
5
ranko D
ranko W
ranko A
kotori W
kotori W

输出: 

vanquish!
out of bounds!
peaceful.
ranko wins!
unexisted empire.

说明:

初始棋盘如下图：

第一回合，ranko从(1,1)移动到(1,2)，占领了一个新格子。
第二回合，ranko试图向上移动，但即将出地图边界，移动失败。
第三回合，ranko向左返回(1,1)。
第四回合，kotori向上移动到(1,2)，由于(1,2)已经被ranko占领，两个势力火拼，ranko势力范围更大取得胜利，消灭koroti并获得其所有领土。
第五回合，由于kotori已经被消灭，所以无法再移动。

示例2

输入: 

2 2 2
abcd 1 1
abcad 1 2
1
abcd D

输出: 

abcd wins!

说明:

abcd的势力向右移动到(1,2)，和abcad势力火拼，两者势力范围相同，但由于"abcd"字符串的字典序更大，因此获得胜利。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(g++ 7.5.0) 解法, 执行用时: 81ms, 内存消耗: 5968K, 提交时间: 2023-07-24 00:45:43 

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
struct Node{
	int x,y;
}; 
int mp[505][505],x[20005],y[20005],tot[20005],d[20005];
int n,m,k;
string name[20005],tmp;char c;
map<string,int> na;
vector<Node> z[20005]; 
void cq(int a,int b){
	while(!z[b].empty()){
		z[a].push_back(z[b].back());
		mp[z[b].back().x][z[b].back().y]=a;
		z[b].pop_back();
		tot[a]++;
	}
	cout<<name[a]<<" wins!"<<endl;
	d[b]=1;
}
signed main(){
	d[0]=1;
  	cin>>n>>m>>k;
  	int tx,ty,xx,yy;
  	for(int i=1;i<=k;++i){
  		cin>>name[i];
  		na[name[i]]=i;
		cin>>x[i]>>y[i];
		if(mp[x[i]][y[i]]){
			if(name[i]>name[mp[x[i]][y[i]]]){
				d[mp[x[i]][y[i]]]=1;
			}else {
				d[i]=1;
				continue;
			}
		}
		tot[i]=1;
		mp[x[i]][y[i]]=i;
		z[i].push_back({x[i],y[i]});
	}
	int q;
	cin>>q;
	for(int i=1;i<=q;++i){
		cin>>tmp>>c;
		tx=na[tmp];
		if(d[tx]){
			cout<<"unexisted empire."<<endl;
		}else {
			xx=x[tx],yy=y[tx];
			if(c=='W')xx-=1;
			if(c=='S')xx+=1;
			if(c=='A')yy-=1;
			if(c=='D')yy+=1;
			if(xx<1||xx>n||yy<1||yy>m){
				cout<<"out of bounds!"<<endl;
			}else if(mp[xx][yy]==0){
				mp[xx][yy]=tx;
				tot[tx]++;
				x[tx]=xx,y[tx]=yy;
				cout<<"vanquish!"<<endl;	
				z[tx].push_back({xx,yy});
			}else if(mp[xx][yy]==tx){
				x[tx]=xx,y[tx]=yy;
				cout<<"peaceful."<<endl;
			}else{
				if(tot[tx]>tot[mp[xx][yy]]||(tot[tx]==tot[mp[xx][yy]]&&name[tx]>name[mp[xx][yy]])){
					cq(tx,mp[xx][yy]);
				}else{
					cq(mp[xx][yy],tx);
				}
				x[tx]=xx,y[tx]=yy;
			} 
		} 
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 85ms, 内存消耗: 4740K, 提交时间: 2023-07-23 20:26:57 

#include <bits/stdc++.h>
using namespace std;
struct dd{
	int x,y;
}; 
int M[505][505],n,m,k,X[20005],Y[20005],tot[20005],D[20005];
string name[20005],tmp;char c;
map<string,int> N;
vector<dd> z[20005]; 
void cq(int a,int b){
	while(!z[b].empty()){
		z[a].push_back(z[b].back());
		M[z[b].back().x][z[b].back().y]=a;
		z[b].pop_back();
		tot[a]++;
	}
	cout<<name[a]<<" wins!"<<endl;
	D[b]=1;
}
int main(){
	D[0]=1;
  	cin>>n>>m>>k;
  	int x,y,xx,yy;
  	for(int i=1;i<=k;++i){
  		cin>>name[i];
  		N[name[i]]=i;
		cin>>X[i]>>Y[i];
		if(M[X[i]][Y[i]]){
			
			if(name[i]>name[M[X[i]][Y[i]]])D[M[X[i]][Y[i]]]=1;
				else {
					D[i]=1;continue;
				}
		}
		tot[i]=1;
		M[X[i]][Y[i]]=i;
		z[i].push_back({X[i],Y[i]});
	}
	int q;
	cin>>q;
	for(int i=1;i<=q;++i){
		cin>>tmp>>c;
		x=N[tmp];
		if(D[x]){
			printf("unexisted empire.\n");
		}else {
			xx=X[x],yy=Y[x];
			if(c=='W')xx-=1;
			if(c=='S')xx+=1;
			if(c=='A')yy-=1;
			if(c=='D')yy+=1;
			if(xx<1||xx>n||yy<1||yy>m)printf("out of bounds!\n");
			else if(M[xx][yy]==0){
				M[xx][yy]=x;tot[x]++;
				X[x]=xx,Y[x]=yy;
				printf("vanquish!\n");	
				z[x].push_back({xx,yy});
			}else if(M[xx][yy]==x){
				X[x]=xx,Y[x]=yy;
				printf("peaceful.\n");
			}else{
				if(tot[x]>tot[M[xx][yy]]||(tot[x]==tot[M[xx][yy]]&&name[x]>name[M[xx][yy]]))cq(x,M[xx][yy]);
				else cq(M[xx][yy],x);
				X[x]=xx,Y[x]=yy;
			} 
			
		} 
	}
	return 0;
}

上一题

© 2025 nowcoder.com