PKU_ACM_1164_The Castle

2023-11-27 08:32
文章标签 acm pku castle 1164

本文主要是介绍PKU_ACM_1164_The Castle，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.pku.edu.cn/JudgeOnline/problem?id=1164  原题

 

类似于迷宫搜索的简单题

 

  2. import java.io.*;
  3. import java.util.*;
  5. public class Main
  6. {
  7.     static Room[][] matrix;
  8.     static int row;
  9.     static int col;
  10.     public static void main(String[] args) throws Exception
  11.     {
  12.         readFile();
  13.         for(int i=0; i<row; i++)
  14.         {
  15.             for(int j=0; j<col; j++)
  16.             {
  17.                 if(!matrix[i][j].bFlag)
  18.                 {
  19.                     process(i,j);
  20.                     sumCount++;
  21.                     if(maxCount>INF)
  22.                     {
  23.                         INF = maxCount;
  24.                     }
  25.                     maxCount=0;
  26.                 }
  27.             }
  28.         }
  29.         System.out.print(sumCount);
  30.         System.out.print("/n"+INF);
  31.     }
  33.     public static void readFile() throws Exception
  34.     {
  35.         BufferedReader br = new BufferedReader(
  36.             new InputStreamReader(System.in));
  37.         StringTokenizer st = null;
  38.         row = Integer.valueOf(br.readLine());
  39.         col = Integer.valueOf(br.readLine());
  40.         matrix = new Room[row][col];
  41.         int count = 0;
  42.         while(count<row)
  43.         {
  44.             st = new StringTokenizer(br.readLine()," ");
  45.             int j = 0;
  46.             Room room = null;
  47.             while(st.hasMoreTokens())
  48.             {
  49.                 room = new Room(Integer.valueOf(st.nextToken()));
  50.                 matrix[count][j] = room;
  51.                 j++;
  52.             }
  53.             count++;
  54.         }
  55.     }
  57.     static void displayRoom()
  58.     {
  59.         for(int i=0; i<row; i++)
  60.         {
  61.             for(int j=0; j<col; j++)
  62.                 System.out.println(matrix[i][j]);
  63.             System.out.println();
  64.         }
  65.     }
  68.     static int sumCount = 0;
  69.     static int maxCount = 0;
  70.     static int INF = 0;
  71.     static void process(int i,int j)
  72.     {
  73.         if(i<0 || j<0 || i>=row || j>=col)
  74.             return;
  75.         if(matrix[i][j].bFlag)
  76.             return;
  77.         maxCount++;
  78.         matrix[i][j].bFlag = true;
  79.         if(matrix[i][j].states[0][1]==2)
  80.         {
  81.             process(i-1,j);
  82.         }
  83.         if(matrix[i][j].states[1][2]==2)
  84.         {
  85.             process(i,j+1);
  86.         }
  87.         if(matrix[i][j].states[2][1]==2)
  88.         {
  89.             process(i+1,j);
  90.         }
  91.         if(matrix[i][j].states[1][0]==2)
  92.         {
  93.             process(i,j-1);
  94.         }
  95.         
  96.         
  97.     }
  99.     
  100.     static class Room
  101.     {
  102.         int[][] states = new int[3][3];
  103.         boolean bFlag = false;
  104.         Room(int flag)
  105.         {
  106.             states[1][1] = 1;
  107.             switch(flag)
  108.             {
  109.             case 0:
  110.                 states[0][1] = 2;
  111.                 states[1][2] = 2;
  112.                 states[1][0] = 2;
  113.                 states[2][1] = 2;
  114.                 break;
  115.             case 1:
  116.                 states[0][1] = 2;
  117.                 states[1][2] = 2;
  118.                 states[2][1] = 2;
  119.                 break;
  120.             case 2:
  121.                 states[1][0] = 2;
  122.                 states[1][2] = 2;
  123.                 states[2][1] = 2;
  124.                 break;
  125.             case 3:
  126.                 states[1][2] = 2;
  127.                 states[2][1] = 2;
  128.                 break;
  129.             case 4:
  130.                 states[0][1] = 2;
  131.                 states[1][0] = 2;
  132.                 states[2][1] = 2;
  133.                 break;
  134.             case 5:
  135.                 states[0][1] = 2;
  136.                 states[2][1] = 2;
  137.                 break;
  138.             case 6:
  139.                 states[1][0] = 2;
  140.                 states[2][1] = 2;
  141.                 break;
  142.             case 7:
  143.                 states[2][1] = 2;
  144.                 break;
  145.             case 8:
  146.                 states[0][1] = 2;
  147.                 states[1][0] = 2;
  148.                 states[1][2] = 2;
  149.                 break;
  150.             case 9:
  151.                 states[0][1] = 2;
  152.                 states[1][2] = 2;
  153.                 break;
  154.             case 10:
  155.                 states[1][0] = 2;
  156.                 states[1][2] = 2;
  157.                 break;
  158.             case 11:
  159.                 states[1][2] = 2;
  160.                 break;
  161.             case 12:
  162.                 states[0][1] = 2;
  163.                 states[1][0] = 2;
  164.                 break;
  165.             case 13:
  166.                 states[0][1] = 2;
  167.                 break;
  168.             case 14:
  169.                 states[1][0] = 2;
  170.                 break;
  171.             case 15:
  172.                 break;
  173.             }
  174.         }
  176.         public String toString()
  177.         {
  178.             for(int i=0; i<3; i++)
  179.             {
  180.                 for(int j=0; j<3; j++)
  181.                     System.out.print(states[i][j] + " ");
  182.                 System.out.println();
  183.             }
  184.             return "";
  185.         }
  186.     }
  187. }

这篇关于PKU_ACM_1164_The Castle的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/427367。

相关文章

认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
【转载】ACM感悟

【转载】ACM感悟

今天看了一篇我们学校前辈的ACM的感悟，觉得写的十分有道理，这里转载，文章还会不断的改进和更新。 原文链接：http://www.cnblogs.com/Chierush/p/3760870.html?ADUIN=1339764596&ADSESSION=1401536826&ADTAG=CLIENT.QQ.5329_.0&ADPUBNO=26349 声明：本文是写给弱校ACM新手的一点
阅读更多...
我们依旧在追梦的路上-山东省第六届ACM比赛总结

我们依旧在追梦的路上-山东省第六届ACM比赛总结

这场比赛从结果而言达到了预期（金牌），从过程而言和我的预期相差甚远（打的太乱，个人发挥很差），还好关键时刻队友抗住压力，负责后果真的不堪设想。 热身赛 热身赛纯粹测机器的，先把A,B,C草草水过（A题小写x打成大写的也是醉了），我和老高开始各种测机器，long long不出所料是lld的，试了一下除0和数组越界的re问题，发现没有re，只有wa（甚至数组越界还AC了），至于栈深的话也没过多追
阅读更多...
ACM东北地区程序设计大赛

ACM东北地区程序设计大赛

不得不说随着参赛级别的提高，题目真的是越来越难啊，不过队长真是给力啊，在我们三个共同努力之下拿下了地区赛三等奖，哈哈我们可是大一唯一一只获奖队，终于在这次比赛打败了田大神。。。大神是失手了，俺和他差距还是挺大的。。。队友陈彤马上要去服兵役了，他说这是我们送给他最好的离别礼物，希望那家伙在部队好好干，以后谁干揍我！！！东北地区赛结束后，今年已经估计没机会参加亚洲区比赛了，赶紧补高数和线数啊！！别挂了
阅读更多...
ACM比赛中如何加速c++的输入输出？如何使cin速度与scanf速度相当？什么是最快的输入输出方法？

ACM比赛中如何加速c++的输入输出？如何使cin速度与scanf速度相当？什么是最快的输入输出方法？

在竞赛中，遇到大数据时，往往读文件成了程序运行速度的瓶颈，需要更快的读取方式。相信几乎所有的C++学习者都在cin机器缓慢的速度上栽过跟头，于是从此以后发誓不用cin读数据。还有人说Pascal的read语句的速度是C/C++中scanf比不上的，C++选手只能干着急。难道C++真的低Pascal一等吗？答案是不言而喻的。一个进阶的方法是把数据一下子读进来，然后再转化字符串，这种方法传说中
阅读更多...
2014年ACM/ICPC亚洲区现场赛广州赛区总结

2014年ACM/ICPC亚洲区现场赛广州赛区总结

本来不想提这件事的，后来学姐找我谈心时提到这件事，我突然意识到在这件事情上我错了一次，明明答应的去参加这场比赛，最后临时决定不去......其实中间有很多很多原因 1：我和tyh,sxk临时不去主要是广州太远，我们身上money不够，呵呵。。。别笑我们，你以为我们是高富帅啊，去一趟广州消费要2个月的生活费，奖学金又没发，你让我找我妈要她辛辛苦苦挣来的工资吗？！从哈尔滨到广州单来回的火车票每个人就
阅读更多...
【UVa】10600 ACM Contest and Blackout 次小生成树

【UVa】10600 ACM Contest and Blackout 次小生成树

类型：次小生成树 题目大意： 为了举办ACM竞赛，市长决定给所有的n(3 <= n <= 100)所学校提供可靠的电力供应。当且仅当一个学校直接连到电站，或者连到另一个有可靠供应的学校时，才有可靠供应。现在给出在不同学校之间的布线成本，找出最便宜的两种连线方案。一个方案的成本等于其中所有学校之间连线的成本的总和。 题目分析： 次小生成树。 先求出最小生成树，然后枚举所有不在
阅读更多...
acm 学习总结

acm 学习总结

最近也是新做了几个题目有的通过看题解然后自己敲出来一遍一遍的修改对动态规划也是有了点认识在拿到一个题目考虑他的思路时如果没法找到每个子问题之间的关系并且用数组将他们记忆就说明这个思路是错的而且题目有很多都是根据一个知识点不断的变式。每种类型的题也都有模板最近我在专门看这些模板，模板看的我也是一脸懵，其实我觉得模板这东西说好也好说不好也不好，好的时候你看出来哪种题适合哪种模板套进去题目就ac了，但是
阅读更多...
ACM STL之vector

ACM STL之vector

vector 是向量 也成动态数组既数组的大小可以根据数据自动变化。使用时要包含头文 定义 vector<类型>变量名; 初始化 vectora; vectorb(a);把a的所有元素给b(必须要同类型)。/vectorb=a; vectora(n,m);a包含n个元素每个元素都为m。 vectora(n);包含n个元素初始化为0。 vectora{b,c,d,e,f};包含花括号中个数的元素，每
阅读更多...
ACM STL之map

ACM STL之map

map是一个容器，里面存储的是 pair 由key和value组成 key称为关键字(对应first)value称为键值（对应second） key值不能重复map中的元素按key升序排列（省了sort）。 头文件 #include 定义 map<int,int>a; 迭代器 map<string,int>::iterator it; 用迭代器调key 和value的用法 it->first it
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2