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竞赛解决方案 测试是使用kawigi edit构建的。
你可以通过这道题去了解Topcoder的题目以及比赛形式
关于TopCoder的竞赛指导，不仅仅是SRM，还有Bug Race、软件比赛的资料，是我从网上收集的，大部分是中文的
TopCoder SRM程序 我尝试过的TopCoder SRM程序列表。 在大多数时候，比赛时间与我的工作/其他活动冲突，因此我对TopCoder不太活跃。 但是我尽力去参加比赛，因为这很有趣。 就像在任何在线比赛中所期望的那样，代码...
topcoder-srm 顶级编码器srm问题集锦
Topcoder软件比赛注册方法和平台使用 Topcoder算法大赛客户端安装流程 Topcoder算法大赛客户端登陆及使用 Topcoder算法大赛注册流程 Topcoder图形比赛注册方法和平台使用
适合topcoder新手
topcoder竞赛的算法讲座ppt
TopCoder比赛登录使用的客户端，需要配置Java环境
topcoder arena,包含ContestAppletProd.jnlp，CodeProcessor.jar,FileEdit.jar,TZTester,运行需要jre环境
TopCoder新手入门指南，一步步操作既可以了，然后开启您的Topcoder编程之旅吧。
Topcoder的Java客户端，安装前确定已经安装了JRE
用于topcoder的第3方编辑器插件。
TopCoper SmartWordToy problem 解决方法，C++源码。 Problem Statement The toy company "I Can't Believe It Works!...Form: http://community.topcoder.com/stat?c=problem_statement&pm=3935&rd=6532
给新手提供的TopCoder注册方法和平台使用 十分详细
topcoder的比赛作品，编译通过的。可以放心使用。
topcoder入门，对想做tc，但又不知道怎么搞的很有帮助，我首先也不知道搞。
这是一类关于acm学习的资料，它详细的说明了Acm学习的内容，如何提高编写软件的能力
关于TopCoder的一些程序竞赛的相关资料
topcoder的在线答题系统