2013-06-19没有注册：没有去做做题，不知道对不对,还没在TopCoder上做过题。
----------------------------------------------------------------------------------------------------
看成是N(N= String.length *String.length)个点无向图；每个顶点有与其相邻的cell的边
即变成寻找图中所有点对的最短路径，（没有负权回路的最短路径是可以动态规划的，Wall-shell算法（希望没写错）复杂度O(N^3)，也可以进行N次Dijkstra计算，使用Dijkstra算法可以用双向Dijkstra )
Alic需要选择的是所有点对的路径中的，某个点的最长路径最小的点既可（从图中看，即图的中心，到达其他点的最短路径的最大值最小）
在实际搜索过程中，可以增加 分支限界的过程，如Cost(p1,p2)>MIN_VALUE,即可终止，这样应该对算法实际效率提高很多。
|
-------------------------------------------------------------------------------------------------------------------------------------
2013-06-20:今天具体实现 如下，明天继续修改，采用图论中的dijkstra过程试一试
郁闷，折腾了1天也没有搞定耗时，下面的程序能正确输出结果，但是耗时比较长
算法复杂度太高:
O(N^3),N = m*n，m为行数，n为列数，即N = 使用的算法，基本是Floyd-Warshell算法，但是这里有个小区别
int dist = opt[i][k] + opt[k][j] - opt[k][k];
而常见最短路径的算法则是：
int dist = opt[i][k] + opt[k][j];
实现思路：算法主要在game2中实现
将每个cell映射成一个顶点，初始化各顶点的值，并初始化cell与相邻cell的边的值
cell(x,y) = 1 --->opt(x*n+y,x*n+y) =1;
Edge of cell(x,y) cell(x-1,y) = 1 --->opt[x*n+y,(x-1)*n]=1;
public class GameOnBoard {
public static void main(String args[]) {
String cost[][] =
{
{"11",
"10"
},
{
"01",
"10"
},
{
"111001",
"001000",
"111111",
"001111",
"001100",
"001011",
"111001",
"010011"
},
{
"001001101011",
"110011001101",
"111111000001",
"111101010001",
"011100101111",
"110010111000",
"111111110101",
"111011110111",
"111100100011",
"000000000110",
"101011011110",
"011111000111",
"101111001011"
},
{
"110010100101010110100010001100111011",
"001000000110100011010100000001001000",
"011000110111101001011101110111000100",
"111001011000100101111010100110110011",
"111000011101001010000100001010000010",
"111001110010100101000001001100011011",
"111110100111010101100000100111000111",
"011111111100100111111110000001110111",
"110000010101001111100011110000001000",
"010010110111111100011101100000011010",
"110001100001111001101000101110110001",
"110010000111011110000010110111010101",
"100100110101001001101000001101101101",
"001011101101001100111110101111001110",
"111010111111111100110100000011111100",
"110101101000001001000100101011100000",
"011011001011010001001000100000110101",
"011111111100000011010111010011010100",
"111001111110001110001110010100111010",
"000001111000001100101010000001101110",
"010000110000010010111110111000010101",
"100010010100110011000111101001101011",
"111010110001101011010001111101111100",
"000111110000110000000101100101000110",
"110000010111001001110001101010111100",
"011111101101001011011010011111100010",
"110101111101010100110010000011001101",
"101101111001010100101111100001110001",
"000110010100101111011011110010010010",
"110101010011101000111011100000010011",
"110001010001110011010100110000010001",
"111010101100111100100011001101010100",
"011000000000100001011010000100010001",
"100000110110000001010001001111010000",
"100011111110010011011011001110011111",
"101100001111100101001101100000100001",
"010000111011010110011001110011111000",
"100010100111110111001010100101111010",
"000110011110111011111000101000001000"
}
};
GameOnBoard game = new GameOnBoard();
for(int i=0;i<cost.length;i++)
System.out.println(game.optimalChoice(cost[i]));
}
int optimalChoice(String cost[]) {
int M = cost.length;
int N = cost[0].length();
byte matrix[][] = new byte[M ][ N ];
for (int i = 0; i < M; i++) {
for (int k = 0; k < N; k++) {
if (cost[i].charAt(k) == '1') {
matrix[i ][k] = 1;
} else
matrix[i ][k] = 0;
}
}
return game2(matrix,M,N);
}
int game2(byte[][] matrix,int m,int n) {
byte minChooseCost = Byte.MAX_VALUE;
int N = m * n;
byte opt[][] = new byte[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
opt[i][j] = Byte.MAX_VALUE;
}
}
for (int i = 0; i < N; i++) {
opt[i][i] = matrix[i / n][i - i / n * n];
}
for (int i = 0; i < N; i++) {
// opt[i][k] 和opt[k][j];是否相邻
int x1 = i / n;
int y1 = i - x1 * n;
int x2;
int y2;
x2 = x1;
y2 = y1 - 1;
if (y2 >= 0) {
int j = x2 * n + y2;
opt[i][j] = (byte) (opt[i][i] + opt[j][j]);
}
y2 = y1 + 1;
if (y2 < n) {
int j = x2 * n + y2;
opt[i][j] = (byte) (opt[i][i] + opt[j][j]);
}
y2 = y1;
x2 = x1 - 1;
if (x2 >= 0) {
int j = x2 * n + y2;
opt[i][j] = (byte) (opt[i][i] + opt[j][j]);
}
x2 = x1 + 1;
if (x2 < m) {
int j = x2 * n + y2;
opt[i][j] = (byte) (opt[i][i] + opt[j][j]);
}
}
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
{
int dist = opt[i][k] + opt[k][j] - opt[k][k];
if (dist < opt[i][j])
opt[i][j] = (byte) dist;
}
}
}
}
minChooseCost = Byte.MAX_VALUE;
//byte max[] = new byte[N];
byte max;
for (int i = 0; i < N; i++) {
max=0;
for (int j = 0; j < N; j++) {
if (max < opt[i][j]) {
max = opt[i][j];
}
}
if (minChooseCost > max)
minChooseCost = max;
}
return minChooseCost;
}
}
2013-06-21 终于有所提高了（还将继续提升下）：采用了Dijkstra过程，（说起来真丢人，我还算是做A*，Dijkstra的专业人士）
-------------------------------------------------------------------------------------------------------------------------------
import java.util.Comparator;
public class GameOnBoard {
public static void main(String args[]) {
String cost[][] =
{
{
"11",
"10"
},
{
"01",
"10"
},
{
"111001",
"001000",
"111111",
"001111",
"001100",
"001011",
"111001",
"010011"
},
{
"001001101011",
"110011001101",
"111111000001",
"111101010001",
"011100101111",
"110010111000",
"111111110101",
"111011110111",
"111100100011",
"000000000110",
"101011011110",
"011111000111",
"101111001011"
},
{
"110010100101010110100010001100111011",
"001000000110100011010100000001001000",
"011000110111101001011101110111000100",
"111001011000100101111010100110110011",
"111000011101001010000100001010000010",
"111001110010100101000001001100011011",
"111110100111010101100000100111000111",
"011111111100100111111110000001110111",
"110000010101001111100011110000001000",
"010010110111111100011101100000011010",
"110001100001111001101000101110110001",
"110010000111011110000010110111010101",
"100100110101001001101000001101101101",
"001011101101001100111110101111001110",
"111010111111111100110100000011111100",
"110101101000001001000100101011100000",
"011011001011010001001000100000110101",
"011111111100000011010111010011010100",
"111001111110001110001110010100111010",
"000001111000001100101010000001101110",
"010000110000010010111110111000010101",
"100010010100110011000111101001101011",
"111010110001101011010001111101111100",
"000111110000110000000101100101000110",
"110000010111001001110001101010111100",
"011111101101001011011010011111100010",
"110101111101010100110010000011001101",
"101101111001010100101111100001110001",
"000110010100101111011011110010010010",
"110101010011101000111011100000010011",
"110001010001110011010100110000010001",
"111010101100111100100011001101010100",
"011000000000100001011010000100010001",
"100000110110000001010001001111010000",
"100011111110010011011011001110011111",
"101100001111100101001101100000100001",
"010000111011010110011001110011111000",
"100010100111110111001010100101111010",
"000110011110111011111000101000001000"
}
};
GameOnBoard game = new GameOnBoard();
long start = System.currentTimeMillis();
for(int i=0;i<cost.length;i++)
System.out.println(game.optimalChoice(cost[i]));
long end = System.currentTimeMillis();
System.out.print("cost time"+(end-start));
}
int optimalChoice(String cost[]) {
int M = cost.length;
int N = cost[0].length();
byte matrix[][] = new byte[M ][ N ];
for (int i = 0; i < M; i++) {
for (int k = 0; k < N; k++) {
if (cost[i].charAt(k) == '1') {
matrix[i ][k] = 1;
} else
matrix[i ][k] = 0;
}
}
return game(matrix,M,N);
}
int game(byte[][] matrix, int M, int N) {
int max = Integer.MIN_VALUE;
int minChooseCost = Integer.MAX_VALUE;
// Dijkstra process();
MyPriorityQueue pq = new MyPriorityQueue(1023);
PriorityQueueItem[] pool = new PriorityQueueItem[M * N];
for (int i = 0; i < pool.length; i++) {
pool[i] = new PriorityQueueItem();
pool[i].index = i;
}
for (int i = 0; i < M * N; i++) {
pq.Clear();
for (int j = 0; j < pool.length; j++) {
pool[j].clearFlag();
}
PriorityQueueItem item = pool[i];
item.parentIndex = -1;
int x = i / N;
int y = i - x * N;
item.cost = matrix[x][y];
item.index = i;
item.setInOpen();
pq.add(item);
max = Integer.MIN_VALUE;
while (!pq.empty()) {
item = pq.top();
pq.popheap();
item.setNotInOpen();
item.setInClose();
// find the 4 adjacent cell if available,add them to priority
// queue;
//System.out.print(item.cost);
max = item.cost;
// for each adjacent cell, push into priority queue, if possible.
int cell_i = item.index / N;
int cell_j = item.index - cell_i * N;
int cell_2_i = -1;
int cell_2_j = -1;
// cell 1
cell_2_i = cell_i;
cell_2_j = cell_j - 1;
if (cell_2_j >= 0) {
int newNodeCost = matrix[cell_2_i][cell_2_j];
PriorityQueueItem newItem = pool[cell_2_i * N + cell_2_j];
int newCost = item.cost + newNodeCost;
if (!newItem.isInClose()) {
if (newItem.isInOpen()) {
if (newItem.cost > newCost) {
newItem.cost = newCost;
pq.EditItem(newItem);
}
} else {
newItem.cost = newCost;
pq.add(newItem);
newItem.setInOpen();
}
}
}
// cell 2
cell_2_i = cell_i;
cell_2_j = cell_j + 1;
if (cell_2_j < N) {
int newNodeCost = matrix[cell_2_i][cell_2_j];
PriorityQueueItem newItem = pool[cell_2_i * N + cell_2_j];
int newCost = item.cost + newNodeCost;
if (!newItem.isInClose()) {
if (newItem.isInOpen()) {
if (newItem.cost > newCost) {
newItem.cost = newCost;
pq.EditItem(newItem);
}
} else {
newItem.cost = newCost;
pq.add(newItem);
newItem.setInOpen();
}
}
}
// cell 3
cell_2_i = cell_i - 1;
cell_2_j = cell_j;
if (cell_2_i >= 0) {
int newNodeCost = matrix[cell_2_i][cell_2_j];
PriorityQueueItem newItem = pool[cell_2_i * N + cell_2_j];
int newCost = item.cost + newNodeCost;
if (!newItem.isInClose()) {
if (newItem.isInOpen()) {
if (newItem.cost > newCost) {
newItem.cost = newCost;
pq.EditItem(newItem);
}
} else {
newItem.cost = newCost;
pq.add(newItem);
newItem.setInOpen();
}
}
}
// cell 4
cell_2_i = cell_i + 1;
cell_2_j = cell_j;
if (cell_2_i < M) {
int newNodeCost = matrix[cell_2_i][cell_2_j];
PriorityQueueItem newItem = pool[cell_2_i * N + cell_2_j];
int newCost = item.cost + newNodeCost;
if (!newItem.isInClose()) {
if (newItem.isInOpen()) {
if (newItem.cost > newCost) {
newItem.cost = newCost;
pq.EditItem(newItem);
}
} else {
newItem.cost = newCost;
pq.add(newItem);
newItem.setInOpen();
}
}
}
}
//System.out.println("\n------------------"+i+"will be "+max);
// the maximum value can found,minmize it
if (minChooseCost > max)
minChooseCost = max;
}
return minChooseCost;
}
int game2(byte[][] matrix,int m,int n) {
byte minChooseCost = Byte.MAX_VALUE;
int N = m * n;
byte opt[][] = new byte[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
opt[i][j] = Byte.MAX_VALUE;
}
}
for (int i = 0; i < N; i++) {
opt[i][i] = matrix[i / n][i - i / n * n];
}
for (int i = 0; i < N; i++) {
// opt[i][k] 和opt[k][j];是否相邻
int x1 = i / n;
int y1 = i - x1 * n;
int x2;
int y2;
x2 = x1;
y2 = y1 - 1;
if (y2 >= 0) {
int j = x2 * n + y2;
opt[i][j] = (byte) (opt[i][i] + opt[j][j]);
}
y2 = y1 + 1;
if (y2 < n) {
int j = x2 * n + y2;
opt[i][j] = (byte) (opt[i][i] + opt[j][j]);
}
y2 = y1;
x2 = x1 - 1;
if (x2 >= 0) {
int j = x2 * n + y2;
opt[i][j] = (byte) (opt[i][i] + opt[j][j]);
}
x2 = x1 + 1;
if (x2 < m) {
int j = x2 * n + y2;
opt[i][j] = (byte) (opt[i][i] + opt[j][j]);
}
}
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
{
int dist = opt[i][k] + opt[k][j] - opt[k][k];
if (dist < opt[i][j])
opt[i][j] = (byte) dist;
}
}
}
}
minChooseCost = Byte.MAX_VALUE;
byte max;
for (int i = 0; i < N; i++) {
max=0;
for (int j = 0; j < N; j++) {
if (max < opt[i][j]) {
max = opt[i][j];
}
}
if (minChooseCost > max)
minChooseCost = max;
}
return minChooseCost;
}
static class PriorityQueueItem implements Comparable<PriorityQueueItem>,Comparator<PriorityQueueItem>{
@Override
public int hashCode(){
return index;
}
public boolean equals( PriorityQueueItem e){
return e!=null &&index==e.index;
}
int index;
int parentIndex;
int cost;
byte flag;
public void setInOpen(){
flag |=1;
}
public void setNotInOpen() {
flag &=~1;
}
public void setInClose(){
flag |=2;
}
public boolean isInOpen(){
return (flag &1)!=0;
}
public boolean isInClose(){
return (flag &2)!=0;
}
public void clearFlag(){
flag =0;
}
@Override
public int compareTo(PriorityQueueItem item) {
if(cost == item.cost)return 0;
if(cost<item.cost) return -1;
return 1;
}
@Override
public int compare(PriorityQueueItem o1, PriorityQueueItem o2) {
if(o1==null ||o2==null)
throw new IllegalArgumentException("cannot be null.");
return o1.compareTo(o2);
}
}
static class MyPriorityQueue{
public MyPriorityQueue(int maxSize)
{
this.maxSize = maxSize;
this.data = new PriorityQueueItem[maxSize+1];
cur = 0;
};
void Clear()
{
cur=0;
}
boolean empty(){return cur==0;}
PriorityQueueItem top(){
return data[1];
}
PriorityQueueItem popheap() {
data[1] = data[cur];
cur--;
adjustify(1);
return data[cur+1];
}
void pushheap(PriorityQueueItem elem)
{
cur = cur+1;
if(cur == maxSize)
{
maxSize <<=1;
PriorityQueueItem []pTempData = new PriorityQueueItem [maxSize];
System.arraycopy(pTempData,0,this.data,1,cur);
data = pTempData;
}
int key = cur;
int i;
data[key] = elem;
i = parent(key);
//adjustify(key);
while(i>0)
{
if(elem.compareTo(data[i])<0)
{
//swap i,key
data[0] = data[i];
data[i] = elem;
data[key] = data[0];
key = i;
i = parent(i);
}
else break;
}
}
boolean EditItem(PriorityQueueItem pItem)
{
//对象必须存在
data[0] = pItem;
int i = cur;
for( ;!data[i].equals(data[0]) ;i--);
if(i==0)
{
//没有找到这个元素那么就把这个元素当作新的元素加进来
this.pushheap(pItem);
}
else
{
//找到这个元素 修改它的值
//data[i]->m_dDisToStart = pItem->m_dDisToStart;
//data[i]->m_dSpeed = pItem->m_dSpeed;
//data[i]->m_lWeight = pItem->m_lWeight;
//data[i]->m_pNext = pItem->m_pNext;
//data[i]->m_pParentArcItem = pItem->m_pParentArcItem;
Update(i);
}
return true;
}
void makeheap()
{
//建堆
for (int i = cur/ 2; i >= 1; i--)
{
adjustify(i);
}
}
int getSize(){return cur;}
void makeheap(PriorityQueueItem []data,int size)
{
System.arraycopy(data,0,this.data,1,size);
cur = size;
//建堆
for (int i = cur/ 2; i >= 1; i--)
{
adjustify(i);
}
}
public int parent(int i) { return i / 2; }
public int left(int i) { return i * 2; }
public int right(int i) { return i * 2 + 1; }
//这个是值变小了，向上调整
int Update(int i)
{
data[0] = data[i];//做一个哨兵
int par = parent(i);
while(data[i].compareTo(data[par])<0)
{
//如果子更小，交换
data[i] = data[par];
data[par] = data[0];
i = par;
par = parent(i);
}
return i;
}
//向下调整
void adjustify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l <= cur && data[l].compareTo(data[smallest])<0)
smallest = l;
if (r <= cur && data[r].compareTo(data[smallest])<0)
smallest = r;
if (smallest != i)
{
//swap(data[smallest], data[i]);
data[0] = data[smallest];
data[smallest] = data[i];
data[i] = data[0];
adjustify(smallest);
}
}
PriorityQueueItem[] data;
int maxSize;
int cur;
public void add(PriorityQueueItem item) {
pushheap(item);
}
public PriorityQueueItem poll() {
return popheap();
}
}
}
耗时：（所有列子总耗时1秒中左右，比原来的26秒，快了不少，但还是没达到预期目标要求）
2
1
3
5
7
cost time955
相关推荐
【标题】"topcoder-srm:Topcoder SRM竞赛解决方案" 这个标题暗示了这是一个与Topcoder平台上的Single Round Matches (SRM)竞赛相关的资源集合。Topcoder SRM是全球知名的在线编程竞赛，参赛者需要在限定时间内解决...
"Topcoder SRM 499 第一题详解" Topcoder SRM 499 的第一题是一道简单的 Addition Game 题目，旨在考察程序员对问题的理解和算法设计能力。本文将详细讲解该题目的知识点和解题思路。 题目分析 该题目中，Fox ...
TopCoder是一个全球知名的在线编程竞赛平台，它提供了多种类型的比赛，包括SRM（Single Round Matches）算法竞赛、Bug Race以及软件设计比赛等。 SRM是TopCoder平台的核心部分，它定期举办算法竞赛，参赛者需要在...
TopCoder SRM程序 我尝试过的TopCoder SRM程序列表。 在大多数时候，比赛时间与我的工作/其他活动冲突，因此我对TopCoder不太活跃。 但是我尽力去参加比赛，因为这很有趣。 就像在任何在线比赛中所期望的那样，代码...
《顶级编码器SRM问题集锦》是针对Java开发者，特别是热衷于参加TopCoder算法竞赛的程序员们的一份宝贵资源。这个压缩包文件“topcoder-srm-master”包含了丰富的编程挑战，旨在提升你的编程技能，尤其是对于解决复杂...
【TOPCODER算法PPT1】是一份关于2007年TopCoder竞赛算法讲座的机密文件，它揭示了这个全球知名的编程竞赛平台的核心特点和价值。TopCoder社区是其核心，拥有遍布全球的会员，包括众多活跃的参赛者，涵盖了学生和专业...
【标题】"Topcoder入门"所指的，是全球知名在线编程竞赛平台Topcoder的初学者指南。这个资源集合可能是为了帮助对算法竞赛和软件开发感兴趣的人，特别是那些想要提升编程技能，尤其是ACM（国际大学生程序设计竞赛）...
Topcoder软件比赛注册方法和平台使用 Topcoder算法大赛客户端安装流程 Topcoder算法大赛客户端登陆及使用 Topcoder算法大赛注册流程 Topcoder图形比赛注册方法和平台使用
【标题】：“topcoder客户端及相关插件” 在IT领域，topcoder是一个著名的在线编程竞赛平台，它为开发者提供了一个展示编程技能、参与竞争并提升能力的场所。客户端，特别是“topcoder arena”，是该平台的核心组成...
在IT领域，TopCoder是一个知名的在线编程竞赛平台，它为程序员提供了一个展示技术才华、提升编程技能以及与全球开发者竞技的舞台。注册并参与TopCoder的比赛，不仅能提高自己的编程能力，还能有机会接触到实际项目...
"手把手教你玩SRM"很显然是一份旨在帮助参赛者提升技能的教程资料，SRM通常指的是TopCoder平台上的Single Round Matches，是ACM类在线编程竞赛的一种形式。下面将分别解析两个压缩包子文件的文件内容，它们都是关于...
适合topcoder新手
TopCoder是一个专注于在线程序设计竞赛的平台，它为程序设计爱好者提供了一个展示自己编码能力的舞台，同时也作为一个猎头公司，为业界发掘和选拔优秀的编程人才。在这个平台上，参赛者可以参加不同类型的竞赛，其中...
TopCoder比赛登录使用的客户端，需要配置Java环境
【标题】"TopCoder竞赛资料"揭示了这个压缩包的核心内容是与TopCoder平台上的程序竞赛相关的资源。TopCoder是一个著名的在线编程竞赛平台，它聚集了大量的程序员和算法爱好者，通过竞技的方式提升技能，同时也是选拔...
TopCoder是一个全球知名的在线编程竞赛平台，自2001年成立以来，已与Google、MS、YAHOO、Intel、Motorola和SUN等世界顶级IT公司合作，为参赛者提供了展示编程技能、获得现金奖励以及进入知名企业的机会。通过赞助商...
Topcoder的Java客户端，安装前确定已经安装了JRE
【标题】"TOPCODER比赛作品"所涉及的知识点主要围绕编程竞赛，特别是与TOPOCODER这个全球知名的在线编程竞技平台相关。TopCoder是一个聚集了世界各地程序员的社区，它组织了一系列的算法竞赛，旨在提升参赛者的编程...