Untitled
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...