本文主要是介绍【蓝桥杯】ALGO-184 Collecting Luggage【JAVA】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
问题的描述:
问题描述
2002年1月1日,12个欧洲国家放弃了它们原来的货币,开始使用欧元。从此,在整个欧元区,再也没有了法郎、马克、里拉、基尔德、克朗……,只有欧元。这些国家使用的纸币相同,但是硬币也相同?不完全是这样。每个国家都有一定的自由来制造自己的欧元硬币:
“每个欧元硬币的一面都有同样的欧洲地形,在另一面,成员国可以用自己的图形装饰硬币。无论哪种图形的硬币,都可以在12个成员国的任何地方使用。比如,一个法国公民可以使用含有西班牙国王印记的欧元硬币,在柏林买到一个热狗。”(来源于http://europa.eu.int/euro/html/entry.html)
在2002年1月1日,巴黎唯一的欧元硬币是法国硬币。不久,第一种非法国硬币出现在巴黎。最终,人们可能会认为所有类型的硬币平均分布在12个成员国(其实并不是这样,因为所有国家一直都在发行自己的硬币,所以即使在稳定的情况下,在柏林,德国硬币应该都是最多的)。所以,多久以后芬兰或爱尔兰的硬币才会第一次在意大利南部流通?每种硬币要多久以后才能出现在所有的地方?
因此,你需要写一个程序来模拟欧元硬币在整个欧洲的传播过程。这里使用一种高度简化的模型,考虑单一的欧元面额。给出一个矩形网格,欧洲城市都在格点上,每个城市最多可以有4个邻接的城市(东西南北各一个)。每个城市都属于且仅属于一个国家,而且一个国家所有城市在平面上刚好组成一个矩形。下图是一个含有3个国家、28个城市的地图。
在地图上,国家之间是连通的,但国家之间可能含有洞,这表示海洋或像瑞士、丹麦这样的非欧元区国家。一开始,每个城市都只有一百万个本国的硬币,然后每一天,每个城市都按照它在这一天开始时的余额,将一定量的硬币送给它的所有邻接城市。这”一定量的硬币“指的是对于这个城市目前所拥有的每种图形的硬币,每满1000个就要拿出来一个。
当某个城市中,每种图形的硬币都至少出现了一个,就称这个城市“已经完成”。当一个国家的所有城市都已经完成的时候,就称这个国家已经完成。你的程序需要得出每个国家的完成时间。
输入格式
输入包含多组数据。每组数据的第一行是一个数c,表示国家的个数,接下来c行,每行描述一个国家。对于国家的描述按照以下格式:name xl yl xh yh,其中name是一个最多25个字符的字符串,表示国家名称,(xl, yl)表示这个国家左下角(西南角)的城市坐标,(xh, yh)表示这个国家右上角(东北角)的城市坐标。
最后一组数据之后是一个0。
输出格式
对于每组数据,先输出一行表示数据编号,接下来对每个国家输出一行,包括这个国家的名称以及它的完成时间(单位:天)。国家之间按照完成时间递增排序,如果两个国家的完成时间相同,按照国家名称的字典序递增排序。
按照样例输出的格式输出(国家名称之前空3格,国家名称和完成时间之间空3格,样例输出在排版的时候可能出了一点问题)。
样例输入
3
France 1 4 4 6
Spain 3 1 6 3
Portugal 1 1 2 2
1
Luxembourg 1 1 1 1
2
Netherlands 1 3 2 4
Belgium 1 1 2 2
0
样例输出
Case Number 1
Spain 382
Portugal 416
France 1325
Case Number 2
Luxembourg 0
Case Number 3
Belgium 2
Netherlands 2
数据规模和约定
1<=c<=20,1<=xl<=xh<=10,1<=yl<=yh<=10。
code:
import java.util.Scanner;
import java.util.StringTokenizer;public class Main {public static int Size;//记录国家数量public static String[] CountryName;//储存国家名字public static int[][] Area;//存储当前国家的左下角和右上角的坐标public static int[][] NumMoney;//在金币传输模拟时记录当前这种金币在每个城市的数量public static int[] Days;//记录每个国家的每个城市拥有金币时的最短时间public static int[][] Mark;//记录当前这种金币在每个国家传播完成时的所用天数
public static void main(String[] args) {// TODO Auto-generated method stubScanner in = new Scanner(System.in);Size=Integer.parseInt(in.nextLine());int count=1;while(Size!=0) {CountryName=new String[Size];Area=new int[Size][4];Mark=new int[Size][Size];for(int i=0;i<Size;i++) {String str=in.nextLine();StringTokenizer token=new StringTokenizer(str," ");CountryName[i]=token.nextToken();for(int j=0;j<4;j++) {Area[i][j]=Integer.parseInt(token.nextToken());}}if(Size==1) {System.out.println("Case Number "+count);System.out.println(CountryName[0]+" 0");}else {CoinTransSim();System.out.println("Case Number "+count);DaysPrint();}count++;Size=Integer.parseInt(in.nextLine());}}public static void IniNumMoney(int ith) {//当每一种金币传播前,初始化这种金币的状态NumMoney=new int[11][11];for(int i=0;i<11;i++) {for(int j=0;j<11;j++) {NumMoney[i][j]=-1;}}for(int k=0;k<Area.length;k++) {for(int i=Area[k][0];i<=Area[k][2];i++) {for(int j=Area[k][1];j<=Area[k][3];j++) {if(k==ith) NumMoney[i][j]=1000000;else NumMoney[i][j]=0;}}}}public static void CoinTransSim() {//模拟金币传播的过程for(int k=0;k<Size;k++) { IniNumMoney(k);int[][] NumMoneyCopy=new int[11][11];for(int num=1;;num++) {for(int i=0;i<11;i++) {for(int j=0;j<11;j++) {NumMoneyCopy[i][j]=NumMoney[i][j];NumMoney[i][j]=-1;}}for(int i=1;i<11;i++) {for(int j=1;j<11;j++) {if(NumMoneyCopy[i][j]==-1)continue;int self=NumMoneyCopy[i][j]/1000;int up=0,down=0,left=0,right=0;int CNum=0;if(NumMoneyCopy[i-1][j]!=-1) {up=NumMoneyCopy[i-1][j]/1000;CNum++;}if(i<10&&NumMoneyCopy[i+1][j]!=-1) {down=NumMoneyCopy[i+1][j]/1000;CNum++;}if(NumMoneyCopy[i][j-1]!=-1) {left=NumMoneyCopy[i][j-1]/1000;CNum++;}if(j<10&&NumMoneyCopy[i][j+1]!=-1) {right=NumMoneyCopy[i][j+1]/1000;CNum++;}NumMoney[i][j]=NumMoneyCopy[i][j]-CNum*self+up+down+left+right;} }InquireTrans(k,num);if(judgeOver(k))break;}} }public static void InquireTrans(int kth,int date) {//查找并储存每一天当前这种金币传播到的国家,并将时间储存到Mark中for(int k=0;k<Area.length;k++) {if(Mark[kth][k]!=0)continue;boolean judge=false;for(int i=Area[k][0];i<=Area[k][2];i++) {for(int j=Area[k][1];j<=Area[k][3];j++) {if(NumMoney[i][j]!=0) continue;else {judge=true;break;}}if(judge==true)break;}if(judge==false)Mark[kth][k]=date; }}public static boolean judgeOver(int ith) {//判断当前这种金币是否传播完成boolean judge=true;for(int i=0;i<Size;i++) {if(Mark[ith][i]!=0||i==ith)continue;else {judge=false;break;}}return judge;}public static void DaysPrint() {//从Mark中得到每个国家完成的最小天数Days=new int[Size];for(int i=0;i<Size;i++) {int MaxNum=Mark[0][i];for(int j=1;j<Size;j++) {if(MaxNum<Mark[j][i])MaxNum=Mark[j][i];}Days[i]=MaxNum;}boolean[] M=new boolean[Size];for(int i=0;i<Size;i++) {int MinNum=Integer.MAX_VALUE;int Pos=-1;for(int j=0;j<Size;j++) {if(!M[j]) {if(MinNum>Days[j]) {MinNum=Days[j];Pos=j;}else if(MinNum==Days[j]) {if(CountryName[Pos].compareTo(CountryName[j])>0) {MinNum=Days[j];Pos=j;}}}}if(Pos==-1)continue;M[Pos]=true;System.out.println(CountryName[Pos]+" "+MinNum);}}
}
这篇关于【蓝桥杯】ALGO-184 Collecting Luggage【JAVA】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!