Java写的,堆内存爆了,大家说说怎么能处理一下
  • 板块P3395 路障
  • 楼主coder_001
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/12/10 23:02
  • 上次更新2023/11/5 06:18:11
查看原帖
Java写的,堆内存爆了,大家说说怎么能处理一下
346950
coder_001楼主2020/12/10 23:02
package P3395;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

	static int T,N;
	static int[][] g = new int[1001][1001];
	static int[][] visited = new int[1001][1001];
	
	static class Info{
		int x;
		int y;
		public Info(int x, int y) {
			this.x = x;
			this.y = y;
		}
		@Override
		public String toString() {
			return "[" + x + "," + y + "]";
		}
	}
	static Info[] block = new Info[2000];
	
	static int[] dx = {0,1,0,-1};
	static int[] dy = {1,0,-1,0};
	
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("src/P3395/P3395_4.in"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StreamTokenizer st = new StreamTokenizer(br);
		
		st.nextToken();
		T = (int)st.nval;
		
		for (int t=1; t<=T; t++) {
			st.nextToken();
			N = (int)st.nval;
			
			if (N == 1) {
				System.out.println("Yes");
				continue;
			}
			
			for (int i=1; i<=N; i++) {
				for (int j=1; j<=N; j++) {
					g[i][j] = 0;
					visited[i][j] = 0;
				}
			}
			for (int i=1; i<=(2*N-2); i++) {
				st.nextToken();
				int x = (int)st.nval;
				st.nextToken();
				int y = (int)st.nval;
				block[i] = new Info(x,y);
			}
			
			LinkedList<Info> q = new LinkedList<Info>();
			q.addLast(new Info(1,1));
			visited[1][1] = 1;
			int I = 1;
			//g[block[I].x][block[I].y] = 1;
			//I++;
			
			boolean ANS = false;
			
			while(!q.isEmpty()) {
				Info k = q.pollFirst();
				
				if (k.x  == N && k.y == N) {
					ANS = true;
					break;
				}
				
				for (int i=0; i<4; i++) {
					int xx = k.x + dx[i];
					int yy = k.y + dy[i];
					if (xx>0 && yy>0 && xx<=N && yy<=N 
					 && visited[xx][yy]==0 
					 && g[xx][yy]==0) {
						q.addLast(new Info(xx,yy));
						visited[xx][yy] = 1;
					}
				}
				
				if (I <= (2*N-2)) {
					g[block[I].x][block[I].y] = 1;
					I++;
				}
			}
			
			if (ANS) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}
			
		}

	}

}

2020/12/10 23:02
加载中...