Submission #1174303


Source Code Expand

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;

public class Main
{
    public static int[] dx = {1,0,-1,0};
    public static int[] dy = {0,1,0,-1};
    static Scanner sc = new Scanner(System.in);
    //static int[] arr;
    static ArrayList<String> list = new ArrayList<>();
    static int[] capa ;
    static int[] cur;
    static int[][] map;
    static HashSet<Integer> set ;
    static int n,m,k;
    static HashMap<Integer, Integer> car = new HashMap<Integer,Integer>();
    static HashMap<Integer, Integer> destination = new HashMap<Integer,Integer>();

	public static void main(String[] args){
		  //String line = sc.nextLine();
           int H =sc.nextInt();
           int W = sc.nextInt();

           
           int K = sc.nextInt();
           int T= sc.nextInt();
           
           
           map = new int[H+1][W+1];
           for(int i=0; i<K; i++){
        	   int x = sc.nextInt();
        	   int y = sc.nextInt();
        	   int fx = sc.nextInt();
        	   int fy = sc.nextInt();
        	  
        	   car.put(i, x*1000+y);
        	   destination.put(i, fx*1000+fy);
        	   //map[x][y] = 1;
           }
           
           
           boolean o = true;
           for(int i=0; i<T ; i++){
        	   map = new int[H+1][W+1];
        	   for(Map.Entry<Integer, Integer> e:car.entrySet()){
        		   int x = e.getValue()/1000;
        		   int y = e.getValue()%1000;
        		   map[x][y]=1;
        	   }
        	   StringBuilder sb = new StringBuilder();
        	   o = false;
        	   for(Map.Entry<Integer, Integer> e : car.entrySet()){
        		   int num = e.getKey();
        		   int cur = e.getValue();
        		   int x = e.getValue()/1000;
        		   int y = e.getValue()%1000;
        		   int fx = destination.get(num)/1000;
        		   int fy = destination.get(num)%1000;
        		   int dis = Math.abs(fx-x)+Math.abs(fy-y);
        		   if(x==fx&& y == fy){
        			   sb.append("-");
        			   continue;
        		   }
        		   
        		   ArrayList<Integer[]> memo = new ArrayList<>();
        		   for(int j=0; j<4; j++){
        			   int nx = x+dx[j];
        			   int ny = y + dy[j];
        			   int def = Math.abs(fx-nx)+Math.abs(fy-ny);
        			   
        			   if(nx>=1 && nx<=H && ny>=1 && ny<=W && map[nx][ny]==0 
        					    && (checkR(x, j)||checkL(y, j)) ){
        				   
        				   
        				   cur = nx*1000+ny;
//        				   car.put(num, cur);
//        				           				   map[nx][ny]=1;
        				           				memo.add(new Integer[]{def,cur,j});
        				   //sb.append(next(j));
        				   o = true;
        				   //break;
        			   }
        			   
        		   }
        		   if(memo.size()>0){
        			   Collections.sort(memo,(a,b)->a[0]-b[0]);
        			   cur = memo.get(0)[1];
        			   int nn = memo.get(0)[2];
        			   sb.append(next(nn));
        			   car.put(num, cur);
        			   int nx = cur/1000;
        			   int ny = cur%1000;
        			   map[nx][ny]=1;
        		   }
        		   else sb.append("-");
        	   }
        	   if(!o)break;
        	   list.add(sb.toString());
        	   
           }
           
           
           
           System.out.println(list.size());
           for(String s: list)System.out.println(s);

	}
	public  static String next(int i) {
		if(i==0)return "D";
		if(i==1)return "R";
		if(i==2)return "U";
		if(i==3)return "L";
		return "-";
	}
	public static boolean checkR(int x, int j) {
		if(x%2==0 && j==0)return true;
		if(x%2==1 && j==2)return true;
	
		return false;
	}
	public static boolean checkL(int y, int j) {
		if(y%2==0 && j==1)return true;
		if(y%2==1 && j==3)return true;
	
		return false;
	}
	
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User nectar
Language Java8 (OpenJDK 1.8.0)
Score 316
Code Size 3985 Byte
Status AC
Exec Time 1960 ms
Memory 248048 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10 test_11 test_12 test_13 test_14 test_15 test_16 test_17 test_18 test_19 test_20 test_21 test_22 test_23 test_24 test_25 test_26 test_27 test_28 test_29 test_30
Score / Max Score 11 / 50000 11 / 50000 11 / 50000 11 / 50000 11 / 50000 11 / 50000 11 / 50000 11 / 50000 10 / 50000 10 / 50000 11 / 50000 10 / 50000 10 / 50000 11 / 50000 10 / 50000 11 / 50000 10 / 50000 10 / 50000 11 / 50000 10 / 50000 11 / 50000 11 / 50000 11 / 50000 10 / 50000 10 / 50000 10 / 50000 11 / 50000 10 / 50000 10 / 50000 10 / 50000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
test_11 subtask_01_11.txt
test_12 subtask_01_12.txt
test_13 subtask_01_13.txt
test_14 subtask_01_14.txt
test_15 subtask_01_15.txt
test_16 subtask_01_16.txt
test_17 subtask_01_17.txt
test_18 subtask_01_18.txt
test_19 subtask_01_19.txt
test_20 subtask_01_20.txt
test_21 subtask_01_21.txt
test_22 subtask_01_22.txt
test_23 subtask_01_23.txt
test_24 subtask_01_24.txt
test_25 subtask_01_25.txt
test_26 subtask_01_26.txt
test_27 subtask_01_27.txt
test_28 subtask_01_28.txt
test_29 subtask_01_29.txt
test_30 subtask_01_30.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 1504 ms 235156 KB
subtask_01_02.txt AC 1508 ms 235188 KB
subtask_01_03.txt AC 1625 ms 232820 KB
subtask_01_04.txt AC 1491 ms 223740 KB
subtask_01_05.txt AC 1642 ms 176376 KB
subtask_01_06.txt AC 1952 ms 232068 KB
subtask_01_07.txt AC 1683 ms 230948 KB
subtask_01_08.txt AC 1483 ms 236264 KB
subtask_01_09.txt AC 1664 ms 233284 KB
subtask_01_10.txt AC 1431 ms 221320 KB
subtask_01_11.txt AC 1547 ms 238240 KB
subtask_01_12.txt AC 1676 ms 229388 KB
subtask_01_13.txt AC 1553 ms 233788 KB
subtask_01_14.txt AC 1522 ms 248048 KB
subtask_01_15.txt AC 1951 ms 236844 KB
subtask_01_16.txt AC 1683 ms 174584 KB
subtask_01_17.txt AC 1640 ms 225904 KB
subtask_01_18.txt AC 1960 ms 180508 KB
subtask_01_19.txt AC 1702 ms 178116 KB
subtask_01_20.txt AC 1437 ms 233588 KB
subtask_01_21.txt AC 1442 ms 206264 KB
subtask_01_22.txt AC 1366 ms 234264 KB
subtask_01_23.txt AC 1944 ms 176496 KB
subtask_01_24.txt AC 1693 ms 203252 KB
subtask_01_25.txt AC 1924 ms 216152 KB
subtask_01_26.txt AC 1671 ms 225176 KB
subtask_01_27.txt AC 1651 ms 228492 KB
subtask_01_28.txt AC 1720 ms 237748 KB
subtask_01_29.txt AC 1544 ms 237584 KB
subtask_01_30.txt AC 1542 ms 231524 KB