NDD Gist - NDDCoder

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class GridAcid {
	static int a[][];
	static int n, m, count, step;

public static class point {

int x;
		int y;

point() {

}

point(int a, int b) {
			this.x = a;
			this.y = b;
		}

public point checktren() {
			if (this.x - 1 >= 1) {
				if (a[this.x - 1][this.y] == 1) {
					point temp = new point();
					temp.x = this.x - 1;
					temp.y = this.y;
					return temp;
				} else {
					return null;
				}
			} else {
				return null;
			}
		}

public point checkduoi() {
			if (this.x + 1 <= n) {
				if (a[this.x + 1][this.y] == 1) {
					point temp = new point();
					temp.x = this.x + 1;
					temp.y = this.y;
					return temp;
				} else {
					return null;
				}
			} else {
				return null;
			}
		}

public point checkphai() {
			if (this.y + 1 <= m) {
				if (a[this.x][this.y + 1] == 1) {
					point temp = new point();
					temp.x = this.x;
					temp.y = this.y + 1;
					return temp;
				} else {
					return null;
				}
			} else {
				return null;
			}
		}

public point checktrai() {
			if (this.y - 1 >= 1) {
				if (a[this.x][this.y - 1] == 1) {
					point temp = new point();
					temp.x = this.x;
					temp.y = this.y - 1;
					return temp;
				} else {
					return null;
				}
			} else {
				return null;
			}
		}

public void fill(int step) {
			if (this != null) {
				a[this.x][this.y] = 0 - step;
			}
		}

public int check() {
			int min = 0;
			if (this.x + 1 <= n) {
				int temp = a[this.x + 1][this.y];
				if (temp < 0) {
					if (temp < min) {
						min = temp;
					}
				} else {
					return -1;
				}
			} else {
				return -1;
			}
			if (this.x - 1 >= 1) {
				int temp = a[this.x - 1][this.y];
				if (temp < 0) {
					if (temp < min) {
						min = temp;
					}
				} else {
					return -1;
				}
			} else {
				return -1;
			}
			if (this.y + 1 <= m) {
				int temp = a[this.x][this.y + 1];
				if (temp < 0) {
					if (temp < min) {
						min = temp;
					}
				} else {
					return -1;
				}
			} else {
				return -1;
			}
			if (this.y - 1 >= 1) {
				int temp = a[this.x][this.y - 1];
				if (temp < 0) {
					if (temp < min) {
						min = temp;
					}
				} else {
					return -1;
				}
			} else {
				return -1;
			}
			return Math.abs(min);
		}

public static class MyStack {
			private int maxSize;
			private point[] stackArray;
			private int top;

public MyStack(int s) {
				maxSize = s;
				stackArray = new point[maxSize];
				top = -1;
			}

public void push(point j) {
				stackArray[++top] = j;
			}

public point pop() {
				return stackArray[top--];
			}

public boolean isEmpty() {
				return (top == -1);
			}

public boolean isFull() {
				return (top == maxSize - 1);
			}
		}

public static void backtrack(MyStack ms, int step1) {
			MyStack mss = new MyStack(n * m + 2);
			while (!ms.isEmpty()) {
				point temp = ms.pop();
				point p1 = temp.checktren();
				if (p1 != null) {
					mss.push(p1);
					p1.fill(step1);
					count--;
				}
				point p2 = temp.checkduoi();
				if (p2 != null) {
					mss.push(p2);
					p2.fill(step1);
					count--;
				}
				point p3 = temp.checkphai();
				if (p3 != null) {
					mss.push(p3);
					p3.fill(step1);
					count--;
				}
				point p4 = temp.checktrai();
				if (p4 != null) {
					mss.push(p4);
					p4.fill(step1);
					count--;
				}
			}
			if (mss.isEmpty()) {
				step = step1;
				return;
			} else {
				if (count == 0) {
					step = step1;
					return;
				}
				backtrack(mss, step1 + 1);
			}
		}
		
		public static void main(String[] args) throws FileNotFoundException {
			// TODO Auto-generated method stub
			System.setIn(new FileInputStream("src/input2.txt"));
			Scanner sc = new Scanner(System.in);
			int testcase = sc.nextInt();
			for (int x = 1; x <= testcase; x++) {
				n = sc.nextInt();
				m = sc.nextInt();
				point p = new point();
				p.x = sc.nextInt();
				p.y = sc.nextInt();
				point p2 = new point();
				a = new int[n + 2][m + 2];
				count = 0;
				for (int i = 1; i <= n; i++) {
					for (int j = 1; j <= m; j++) {
						a[i][j] = sc.nextInt();
						if (a[i][j] == 1) {
							count++;
						}
						if (a[i][j] == 2) {
							p2.x = i;
							p2.y = j;
						}
					}
				}
				MyStack mss = new MyStack(1);
				mss.push(p);
				System.out.println("Case #" + x);
				backtrack(mss, 2);
				int m = p2.check();
				if (m > 0) {
					System.out.print(m + " ");
					if (count == 0) {
						System.out.println(step);
					} else {
						System.out.println("-1");
					}
				} else {
					System.out.println("-1 -1");
				}
			}
		}
	}
}

Title

Language

Public

View

Cancel

Font size:

Theme