package cn.test4;
import java.util.ArrayList;
import java.util.List;
/**
* 一条贪吃的蛇在一个n*m的网格中游走，它只能从一个方格走向另一个相邻的方格，这里相邻的意思是两个方格有公共边。
* 每个方格可以看作是一个房间，其中一些是空的，一些存放有苹果。
* 贪吃的蛇根本不进入空的房间，而进入有苹果的房间后就可以带走所有苹果使房间成为空的。
* 蛇从一个指定的房间出发，最终回到它的家，把一路带来的苹果存储到家中，当然，它希望带来的苹果最多。
* 请编写程序，输入有整数n和m，及n*m的一个矩阵，矩阵元素数值中有一个是 -1，表示蛇的出发位置，有一个是 -2，表示蛇的家的位置，
* 其余数值是非负整数，0表示房间为空，非零整数表示苹果的数目。输出蛇选择的游走路径和获得的最多的苹果数目。
* 例如输入4*4矩阵：
* 7 0 4 18
* 4 0 1 1
* 15 7 11 -1
* 0 12 -2 0
* 则应输出 (2, 3), (1, 3), (0, 3), (0, 2), (1, 2), (2, 2), (2, 1), (3, 1), (3, 2),
* 带回苹果数为1+18+4+1+11+7+12 = 54。（本题为2011年ACM大赛题目）。
* （可查阅：吕国英，任瑞征等编著，算法设计与分析（第2版），清华大学出版社，2009年1月，第200-202页。
* 提示：这是一个利用回溯算法的迷宫搜索类型问题，可参考类似问题的已有解法。
* @author ffr
*/
public class GreedySnop {
private List<Position> stack = new ArrayList<Position>();
private Integer[][] grid;
/**
* 计算
* @param grid 数组
* @param row 行数
* @param col 列数
*/
public void execute(Integer[][] arg, int row, int col){
grid = arg;
//初始化
stack.add(new Position(2, 3, -1));
grid[2][3] = 0;
while(stack.size() > 0){
Position pos = stack.get(stack.size()-1);
//向上
if(pos.x-1 >= 0 && grid[pos.x-1][pos.y] != 0 && grid[pos.x-1][pos.y] != -2 ){
stack.add(new Position(pos.x-1, pos.y, grid[pos.x-1][pos.y]));
grid[pos.x-1][pos.y] = 0;
continue;
}else if(pos.x-1 >= 0 && grid[pos.x-1][pos.y] == -2){
print(stack);
//向右
if(pos.y+1 < col && grid[pos.x][pos.y+1] != 0 && grid[pos.x][pos.y+1] != -2){
stack.add(new Position(pos.x, pos.y+1, grid[pos.x][pos.y+1]));
grid[pos.x][pos.y+1] = 0;
continue;
}
//向下
if(pos.x+1 < row && grid[pos.x+1][pos.y] != 0 && grid[pos.x+1][pos.y] != -2){
stack.add(new Position(pos.x+1, pos.y, grid[pos.x+1][pos.y]));
grid[pos.x+1][pos.y] = 0;
continue;
}
//向左
if(pos.y-1 >= 0 && grid[pos.x][pos.y-1] != 0 && grid[pos.x][pos.y-1] != -2){
stack.add(new Position(pos.x, pos.y-1, grid[pos.x][pos.y-1]));
grid[pos.x][pos.y-1] = 0;
continue;
}
//走不通，移除最后一个，继续出栈
stack.remove(stack.size()-1);
continue;
}
//向右
if(pos.y+1 < col && grid[pos.x][pos.y+1] != 0 && grid[pos.x][pos.y+1] != -2){
stack.add(new Position(pos.x, pos.y+1, grid[pos.x][pos.y+1]));
grid[pos.x][pos.y+1] = 0;
continue;
}else if(pos.y+1 < col && grid[pos.x][pos.y+1] == -2){
print(stack);
//向下
if(pos.x+1 < row && grid[pos.x+1][pos.y] != 0 && grid[pos.x+1][pos.y] != -2){
stack.add(new Position(pos.x+1, pos.y, grid[pos.x+1][pos.y]));
grid[pos.x+1][pos.y] = 0;
continue;
}
//向左
if(pos.y-1 >= 0 && grid[pos.x][pos.y-1] != 0 && grid[pos.x][pos.y-1] != -2){
stack.add(new Position(pos.x, pos.y-1, grid[pos.x][pos.y-1]));
grid[pos.x][pos.y-1] = 0;
continue;
}
//向上
if(pos.x-1 >= 0 && grid[pos.x-1][pos.y] != 0 && grid[pos.x-1][pos.y] != -2 ){
stack.add(new Position(pos.x-1, pos.y, grid[pos.x-1][pos.y]));
grid[pos.x-1][pos.y] = 0;
continue;
}
stack.remove(stack.size()-1);
continue;
}
//向下
if(pos.x+1 < row && grid[pos.x+1][pos.y] != 0 && grid[pos.x+1][pos.y] != -2){
stack.add(new Position(pos.x+1, pos.y, grid[pos.x+1][pos.y]));
grid[pos.x+1][pos.y] = 0;
continue;
}else if(pos.x+1 < row && grid[pos.x+1][pos.y] == -2){
print(stack);
//向左
if(pos.y-1 >= 0 && grid[pos.x][pos.y-1] != 0 && grid[pos.x][pos.y-1] != -2){
stack.add(new Position(pos.x, pos.y-1, grid[pos.x][pos.y-1]));
grid[pos.x][pos.y-1] = 0;
continue;
}
//向上
if(pos.x-1 >= 0 && grid[pos.x-1][pos.y] != 0 && grid[pos.x-1][pos.y] != -2 ){
stack.add(new Position(pos.x-1, pos.y, grid[pos.x-1][pos.y]));
grid[pos.x-1][pos.y] = 0;
continue;
}
//向右
if(pos.y+1 < col && grid[pos.x][pos.y+1] != 0 && grid[pos.x][pos.y+1] != -2){
stack.add(new Position(pos.x, pos.y+1, grid[pos.x][pos.y+1]));
grid[pos.x][pos.y+1] = 0;
continue;
}
stack.remove(stack.size()-1);
continue;
}
//向左
if(pos.y-1 >= 0 && grid[pos.x][pos.y-1] != 0 && grid[pos.x][pos.y-1] != -2){
stack.add(new Position(pos.x, pos.y-1, grid[pos.x][pos.y-1]));
grid[pos.x][pos.y-1] = 0;
continue;
}else if(pos.y-1 >= 0 && grid[pos.x][pos.y-1] == -2){
print(stack);
//向上
if(pos.x-1 >= 0 && grid[pos.x-1][pos.y] != 0 && grid[pos.x-1][pos.y] != -2 ){
stack.add(new Position(pos.x-1, pos.y, grid[pos.x-1][pos.y]));
grid[pos.x-1][pos.y] = 0;
continue;
}
//向右
if(pos.y+1 < col && grid[pos.x][pos.y+1] != 0 && grid[pos.x][pos.y+1] != -2){
stack.add(new Position(pos.x, pos.y+1, grid[pos.x][pos.y+1]));
grid[pos.x][pos.y+1] = 0;
continue;
}
//向下
if(pos.x+1 < row && grid[pos.x+1][pos.y] != 0 && grid[pos.x+1][pos.y] != -2){
stack.add(new Position(pos.x+1, pos.y, grid[pos.x+1][pos.y]));
grid[pos.x+1][pos.y] = 0;
continue;
}
stack.remove(stack.size()-1);
continue;
}
//哪都走不通，出栈
stack.remove(stack.size()-1);
continue;
}
}
public static void main(String[] args) {
Integer[][] arg = {{7,0,4,18},{4,0,1,1},{15,7,11,-1},{0,12,-2,0}};
new GreedySnop().execute(arg, 4, 4);
System.out.println("ok");
}
public void print(List<Position> stack){
for(Position pos : stack){
System.out.print(pos.print());
}
System.out.println();
}
public Integer sumstack(List<Position> stack){
if(stack == null || stack.size()<=0){
return 0;
}
Integer result = 0;
for(Position pos : stack){
result = result + pos.value;
}
return result;
}
}
/**
* 各个单元
*/
class Position{
public Integer x;
public Integer y;
public Integer value;
public Position() {
super();
}
public Position(Integer x, Integer y, Integer value) {
super();
this.x = x;
this.y = y;
this.value = value;
}
public String print(){
return "("+x+","+y+")";
}
@Override
public String toString(){
return "x:"+x+"y:"+y+"value:"+value;
}
}
/*
运行结果：
(2,3)(1,3)(0,3)(0,2)(1,2)(2,2)
(2,3)(1,3)(0,3)(0,2)(1,2)(2,2)(2,1)(3,1)
(2,3)(1,3)(0,3)(0,2)(1,2)(2,2)
ok
*/