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;
}
}