package srm646; import java.util.Comparator; import java.util.HashSet; import java.util.PriorityQueue; import java.util.Set; public class TheGridDivTwo { //<1>state的比较函数,是"大于>"即大的在前面,属于降序排序 //<2>比较函数在 score-step,这个是启发是搜索策略,可以让搜索,尽量向右搜索,而不是向左,即有一定的方向性。 //当然,如果直接基于score排序,这也是可以的,但性能应该差一些。 static public class State implements Comparator<State>,Comparable<State> { public State() { } public State(int x, int y, int score) { this.x = x; this.y = y; this.score = score; } int x; int y; int score; int step; @Override public int compare(State o1, State o2) { // TODO Auto-generated method stub if (o1.score-o1.step < o2.score-o2.step) { return 1; } if (o1.score-o1.step == o2.score-o2.step) { return 0; } return -1; } @Override public String toString(){ return "{"+x+","+y+","+score+","+step+"}"; } @Override public int hashCode() { return x ^ y; } @Override public boolean equals(Object src) { return src != null && src instanceof State && ((State) src).x == x && ((State) src).y == y; } @Override public int compareTo(State o) { if (score -step< o.score-step) { return 1; } if (score-step == o.score-step) { return 0; } return -1; } } public int find(int[] x, int[] y, int k) { int ans = 0; Set<State> blockedMap = new HashSet<State>(); for (int i = 0; i < x.length; i++) { blockedMap.add(new State(x[i], y[i], 0)); } State start = new State(); start.x = 0; start.y = 0; start.score = 0; start.step = 0; State maxState = new State(0, 0, 0); PriorityQueue<State> pq = new PriorityQueue<State>(); Set<State> visited = new HashSet<State>(); pq.add(start); visited.add(start); while (!pq.isEmpty()) { State cur = pq.poll(); if (cur.step > k) { continue; } if (maxState.score < cur.score) { maxState.score = cur.score; maxState.x = cur.x; maxState.y = cur.y; maxState.step = cur.step; } //后面的得分会更小(这个是分支限界,剪枝策略) if(cur.score + k - cur.step <= maxState.score){ continue; } if (cur.step < k) { // [cur.x+1][cur.y+1] State next = null; next = new State(cur.x + 1, cur.y, cur.score + 1); next.step = cur.step + 1; if (!blockedMap.contains(next)) { if (!visited.contains(next)) { pq.add(next); visited.add(next); } } next = new State(cur.x - 1, cur.y, cur.score -1); next.step = cur.step + 1; if (!blockedMap.contains(next)) { if (!visited.contains(next)) { pq.add(next); visited.add(next); } } next = new State(cur.x, cur.y + 1, cur.score); next.step = cur.step + 1; if (!blockedMap.contains(next)) { if (!visited.contains(next)) { pq.add(next); visited.add(next); } } next = new State(cur.x, cur.y - 1, cur.score); next.step = cur.step + 1; if (!blockedMap.contains(next)) { if (!visited.contains(next)) { pq.add(next); visited.add(next); } } } } System.out.println(maxState); ans = maxState.score; return ans; } public static void main(String args[]) { TheGridDivTwo div2= new TheGridDivTwo(); int ans = div2.find(new int[]{1,1,1,1}, new int[]{-2,-1,0,1},4); System.out.println(ans); ans = div2.find(new int[]{1,0,0,-1,-1,-2,-2,-3,-3,-4,-4}, new int[]{0,-1,1,-2,2,-3,3,-4,4,-5,5},47); System.out.println(ans); } }
这是SRM646 的div2 题,刚开始,比较函数写成了<,后修改为降序排列,但没改正确,检查很多遍都没有发现。
这是一个基本的穷举搜索过程,但在brute-force search中可以加入一些策略,比如启发式的(score-step),这个也算A*,再加入一个限界,用于剪枝
相关推荐
topcoder的数学类算法题目。一个整数被称为k-smooth当且仅当它的最大素因子不大于k,给定N和K,计算出1 - N中有多少个整数是k-smooth。1 , 1 <= K <= 1000.
SRM2Multi dumper for hsap
VMware Virtualization Forum 2009 “业务持续性和灾难恢复”分...——SRM架构和特性,以及路线图 演讲嘉宾:姜大勇 VMware区域客户工程师 (若要下载大会其他部分,点击 标签“2009VMware虚拟化论坛”,即可看到)
omron系列CPM1/CPM1A/CPM2A/CPM2C/SRM1(-V2) PLC编程手册pdf,omron系列CPM1/CPM1A/CPM2A/CPM2C/SRM1(-V2) PLC编程手册
BS ISO IEC 24392-2023 网络安全——工业互联网平台安全参考模型(SRM-IIP).rar
SAP SRM 介绍
SRM210+(PA)SAP+SRM+Server+Configuration+(Col92) 开发配置
Driver HASP SRM emulator (x86)
多年SRM实施经验总结,对希望从事SRM实施或规划的同学们有帮助
srm后端JAVA 供应商平台管理 标准物资开票表 bus_standard_invoice_out增加freeze_quantity(冻结数量这一列)。 标准物资开票表 bus_standard_invoice_out的主键为{行项目、采购订单号、物料凭证}。 标准物资...
分块描述SRM系统的作用:寻源、协同和考核 涉及具体的业务用途,供前期规划作参考,可根据实际情况调整,再考虑如何实现
ASP SRM USB Command Line Dumper Instructions. HASP SRM USB命令行转储指令。 WARNING!!! Before make dump from dongle make sure that you install the original dongle driver. Insert your LPT or USB dongle...
简叙什么是SRM,SRM解决什么问题,SRM有用途,SRM功能等
HASP_SRM_Runtime_setup
SRM210 (PA)SAP SRM Server Configuration (Col92) Configuration
SRM空间富模型隐写分析算法,选区高维特征,使用集成分类器进行训练
SRM Overview中文版让你更直观更容易了解SRM是什么,能做什么
SRM影像分割算法的matlab程序,主函数SRM_new
不仅可以阅读srm格式文件,还可以制作文档。完全绿色破解,是一款不错的srm阅读器。
HASP SRM加密狗简介,阿拉丁公司的各种加密够简介