Untitled

 avatar
unknown
plain_text
2 years ago
2.6 kB
4
Indexable
//cach 1
import java.util.Scanner;

class Queue{
	private int size;
	private int [] arr;
	private int t,b;
	public Queue(int s) {
		size = s;
		arr = new int [size];
		t = -1;
		b = -1;
	}
	public boolean isEmpty() {
		if(t==b) {
			return true;
		}
		return false;
	}
	public void Push(int x) {
		t++;
		arr[t] = x;
	}
	public int Pop() {
		b++;
		return arr[b];
	}
	public void reset() {
		t = b = -1;
	}
}
public class BFS {
	static int n;
	static int map[][];
	static int vis[][];
	static int dx[] = {0,0,1,-1};
	static int dy[] = {1,-1,0,0};
	static Queue Qx = new Queue(10000);
	static Queue Qy = new Queue(10000);
	public static boolean BFS(int x,int y) {
		Qx.reset();
		Qy.reset();
		Qx.Push(x);
		Qy.Push(y);
		vis[x][y] = 1;
		while(!Qx.isEmpty()) {
			int a = Qx.Pop();
			int b = Qy.Pop();
			for (int i = 0; i < 4; i++) {
				int r = a + dx[i] * map[a][b];
				int c = b + dy[i] * map[a][b];
				if(r>=0 && c>=0 && r<n && c<n && map[r][c]!=0 && vis[r][c] == 0) {
					if(r == n-1 && c == n-1) {
						return true;
					}
					vis[r][c] = 1;
					Qx.Push(r);
					Qy.Push(c);
				}
			}
		}
		return false;
	}
	public static void main(String[] args) {
		//System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int t  = sc.nextInt();
		for (int tc = 0; tc < t; tc++) {
			n = sc.nextInt();
			map = new int [n][n];
			vis = new int [n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			if(BFS(0,0)) {
				System.out.println("YES");
			}else {
				System.out.println("NO");
			}
		}
	}
}



//cach2
import java.util.Scanner;

public class DFS {
	static int n;
	static int map[][];
	static int vis[][];
	static int dx[] = {0,0,1,-1};
	static int dy[] = {1,-1,0,0};
	public static boolean DFS(int x,int y) {
		if(x == n-1 && y == n-1) {
			return true;
		}
		for (int i = 0; i < 4; i++) {
			int r = x + dx[i] * map[x][y];
			int c = y + dy[i] * map[x][y];
			if(r>=0 && c>=0 && r<n && c<n && map[r][c]!=0 && vis[r][c] == 0) {
				vis[r][c] = 1;
				if (DFS(r, c)) {
	                return true;
	            }
			}
		}
		return false;
	}
	public static void main(String[] args) {
		//System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int t  = sc.nextInt();
		for (int tc = 0; tc < t; tc++) {
			n = sc.nextInt();
			map = new int [n][n];
			vis = new int [n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			vis[0][0] = 1;
			if(DFS(0,0)) {
				System.out.println("YES");
			}else {
				System.out.println("NO");
			}
		}
	}
}
Editor is loading...