Untitled

package Chan_Robot;



import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;


class MyQueue{
	int input;
	int output;
	Location[] array;
	int maxsize;
	public MyQueue(int maxsize) {
		super();
		this.input = -1;
		this.output = -1;
		this.array = new Location[maxsize];
		this.maxsize = maxsize;
	}
	void push(Location lc){
		input++;
		array[input]=lc;
	}
	Location pop(){
		output++;
		return array[output];
	}
	boolean isEmty(){
		if(input==output){
			return true;
		}
		return false;
	}
	void clear(){
		input=output=-1;
	}
	
	
}
class UserSolution {
	boolean[][] isVisited;
	int[][] island;
	int[][] temp_island;
	int num;
	ArrayList<Area>[] list;
	int[] dx = { 1, 0, -1, 0 };
	int[] dy = { 0, -1, 0, 1 };
	MyQueue q = new MyQueue(1000000);

	public void init(int N, int mMap[][]) {
		num = N;
		island=new int[N+2][N+2];
		temp_island=new int[N+2][N+2];
		for(int i=1 ;i<=N;i++){
			for(int j=1;j<=N;j++){
				temp_island[i][j]=island[i][j]=mMap[i-1][j-1];
			}
		}
		list = new ArrayList[10001];
		for (int i = 0; i <= 10000; i++) {
			list[i] = new ArrayList<Area>();
		}
		int down = 0, reverse = 0;
		for (int len = 2; len <= 5; len++) {
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j + len - 1 <= N; j++) {
					// /Ngang
					down = 0;
					for (int k = 0; k+1 < len; k++) {
						down = down * 10 + island[i][j + k + 1]
								- island[i][j + k] + 5;
					}
					list[down].add(new Area(i, j, true, false));
					reverse = 0;
					for (int k = len - 1; k-1 >= 0; k--) {
						reverse = reverse * 10 + island[i][j + k -1]
								- island[i][j + k] + 5;
					}
					if (reverse != down) {
						list[reverse].add(new Area(i, j, true, true));
					}
					// /doc
					down = 0;
					for (int k = 0; k+1 < len; k++) {
						down = down * 10 + island[j + k + 1][i]
								- island[j + k][i] + 5;
					}
					list[down].add(new Area(j, i, false, false));
					reverse = 0;
					for (int k = len - 1; k-1 >= 0; k--) {
						reverse = reverse * 10 + island[j + k -1][i]
								- island[j + k][i] + 5;
					}
					if (reverse != down) {
						list[reverse].add(new Area(j, i, false, true));
					}
				}
			}
		}

	}

	public int numberOfCandidate(int M, int mStructure[]) {
		if (M == 1) {
			return num * num;
		}
		int hash = 0;
		for (int i = 0; i < M - 1; i++) {
			hash = hash * 10 + mStructure[i] - mStructure[i + 1] + 5;
		}
		return list[hash].size();
	}

	int BFS(int[][] mMap, int mDir) {
		q.clear();
		isVisited=new boolean[num+2][num+2];
		
		if(mDir==0){
			for(int j=1;j<=num;j++){
				q.push(new Location(1, j));
				isVisited[1][j]=true;
			}
		}
		if(mDir==1){
			for(int j=1;j<=num;j++){
				q.push(new Location(j, num));
				isVisited[j][num]=true;
			}
		}
		if(mDir==2){
			for(int j=1;j<=num;j++){
				q.push(new Location(num, j));
				isVisited[num][j]=true;
			}
		}
		if(mDir==3){
			for(int j=1;j<=num;j++){
				q.push(new Location(j, 1));
				isVisited[j][1]=true;
			}
		}
		while(!q.isEmty()){
			Location lc=q.pop();
			for(int i=0;i<4;i++){
				int xx=lc.row+dx[i];
				int yy=lc.col+dy[i];
				if(xx<1 || xx>num || yy<1 ||yy>num|| isVisited[xx][yy]==true) continue;
				if(mMap[xx][yy]>=mMap[lc.row][lc.col]){
					isVisited[xx][yy]=true;
					q.push(new Location(xx, yy));
				}
			}
		}
		int ans=0;
		for(int i=1;i<=num;i++){
			for(int j=1;j<=num;j++){
				if(isVisited[i][j]==false){
					ans++;
				}
			}
		}
		return ans;
	}

	public int maxBlockedRobots(int M, int mStructure[], int mSeaLevel) {
		int ans=-1;
		
		int hash=0;
		for(int i=0;i<M-1;i++){
			hash = hash * 10 + mStructure[i] - mStructure[i + 1] + 5;
		}
		if(list[hash].isEmpty()){
			return -1;
		}
		for(Area candi:list[hash]){
			if(candi.checkNgang){
				int sum;
				if(candi.checkDao){
					sum=mStructure[M-1]+island[candi.r][candi.c];
				}
				else{
					sum=mStructure[0]+island[candi.r][candi.c];
				}
				for(int i=0;i<M;i++){
					temp_island[candi.r][candi.c+i]=sum;
				}
				if(ans<BFS(temp_island, mSeaLevel)){
					ans=BFS(temp_island, mSeaLevel);
				}
				for(int i=0;i<M;i++){
					temp_island[candi.r][candi.c+i]=island[candi.r][candi.c+i];
				}
			}
			else{
				int sum;
				if(candi.checkDao){
					sum=mStructure[M-1]+island[candi.r][candi.c];
				}
				else{
					sum=mStructure[0]+island[candi.r][candi.c];
				}
				for(int i=0;i<M;i++){
					temp_island[candi.r+i][candi.c]=sum;
				}
				if(ans<BFS(temp_island, mSeaLevel)){
					ans=BFS(temp_island, mSeaLevel);
				}
				for(int i=0;i<M;i++){
					temp_island[candi.r+i][candi.c]=island[candi.r+i][candi.c];
				}
			}
		}
		return ans;
	}
}
class Area {
	int r;
	int c;
	boolean checkNgang;
	boolean checkDao;
	public Area(int r, int c, boolean checkNgang, boolean checkDao) {
		super();
		this.r = r;
		this.c = c;
		this.checkNgang = checkNgang;
		this.checkDao = checkDao;
	}
	

	

}

class Location {
	int row;
	int col;

	public Location(int row, int col) {
		super();
		this.row = row;
		this.col = col;
	}

}