fork(1) download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.     static class IntPair{
  5.         int x, y;
  6.  
  7.         public IntPair(int x, int y) {
  8.             this.x = x;
  9.             this.y = y;
  10.         }
  11.     }
  12.  
  13.     static class Edge {
  14.         int t, rev, cap, f;
  15.  
  16.         public Edge(int t, int rev, int cap) {
  17.             this.t = t;
  18.             this.rev = rev;
  19.             this.cap = cap;
  20.         }
  21.     }
  22.  
  23.     public static List<Edge>[] createGraph(int nodes) {
  24.         List<Edge>[] graph = new List[nodes];
  25.         for (int i = 0; i < nodes; i++)
  26.             graph[i] = new ArrayList<>();
  27.         return graph;
  28.     }
  29.  
  30.     public static void addEdge(List<Edge>[] graph, int s, int t, int cap) {
  31.         graph[s].add(new Edge(t, graph[t].size(), cap));
  32.         graph[t].add(new Edge(s, graph[s].size() - 1, 0));
  33.     }
  34.  
  35.     static boolean dinicBfs(List<Edge>[] graph, int src, int dest, int[] dist) {
  36.         Arrays.fill(dist, -1);
  37.         dist[src] = 0;
  38.         int[] Q = new int[graph.length];
  39.         int sizeQ = 0;
  40.         Q[sizeQ++] = src;
  41.         for (int i = 0; i < sizeQ; i++) {
  42.             int u = Q[i];
  43.             for (Edge e : graph[u]) {
  44.                 if (dist[e.t] < 0 && e.f < e.cap) {
  45.                     dist[e.t] = dist[u] + 1;
  46.                     Q[sizeQ++] = e.t;
  47.                 }
  48.             }
  49.         }
  50.         return dist[dest] >= 0;
  51.     }
  52.  
  53.     static int dinicDfs(List<Edge>[] graph, int[] ptr, int[] dist, int dest, int u, int f) {
  54.         if (u == dest)
  55.             return f;
  56.         for (; ptr[u] < graph[u].size(); ++ptr[u]) {
  57.             Edge e = graph[u].get(ptr[u]);
  58.             if (dist[e.t] == dist[u] + 1 && e.f < e.cap) {
  59.                 int df = dinicDfs(graph, ptr, dist, dest, e.t, Math.min(f, e.cap - e.f));
  60.                 if (df > 0) {
  61.                     e.f += df;
  62.                     graph[e.t].get(e.rev).f -= df;
  63.                     return df;
  64.                 }
  65.             }
  66.         }
  67.         return 0;
  68.     }
  69.  
  70.     public static int maxFlow(List<Edge>[] graph, int src, int dest) {
  71.         int flow = 0;
  72.         int[] dist = new int[graph.length];
  73.         while (dinicBfs(graph, src, dest, dist)) {
  74.             int[] ptr = new int[graph.length];
  75.             while (true) {
  76.                 int df = dinicDfs(graph, ptr, dist, dest, src, Integer.MAX_VALUE);
  77.                 if (df == 0)
  78.                     break;
  79.                 flow += df;
  80.             }
  81.         }
  82.         return flow;
  83.     }
  84.  
  85.     static int trad(int m, int x, int y){
  86.         return x*m+y;
  87.     }
  88.  
  89.  
  90.     public static void main(String[] args) {
  91.         Scanner in = new Scanner(System.in);
  92.         int t = in.nextInt();
  93.         while (t-->0){
  94.             int n = in.nextInt();
  95.             int m = in.nextInt();
  96.             char[][]grid = new char[n][m];
  97.             IntPair l = new IntPair(0, 0);
  98.             IntPair c = new IntPair(0, 0);
  99.             for (int i = 0; i < n; i++) {
  100.                 String s = in.next();
  101.                 for (int j = 0; j < m; j++) {
  102.                     grid[i][j] = s.charAt(j);
  103.                     if(grid[i][j]=='L') l = new IntPair(i, j);
  104.                     else if(grid[i][j]=='C') c = new IntPair(i,j);
  105.                 }
  106.             }
  107.             HashSet<Integer> set = new HashSet<>();
  108.             set.add(trad(m, c.x, c.y));
  109.             set.add(trad(m, c.x-1, c.y));
  110.             set.add(trad(m, c.x+1, c.y));
  111.             set.add(trad(m, c.x, c.y-1));
  112.             set.add(trad(m, c.x, c.y+1));
  113.             set.add(trad(m, l.x, l.y));
  114.             List<Edge>[] graph = createGraph(2*n*m);
  115.             for (int i = 0; i < n; i++) {
  116.                 for (int j = 0; j < m; j++) {
  117.                     if(grid[i][j]!='#'){
  118.                         int q = (set.contains(trad(m,i,j)))?5:1;
  119.                         addEdge(graph, trad(m, i, j), trad(m, i, j)+n*m, q);
  120.                         //Arriba
  121.                         if(i>0&&grid[i-1][j]!='#'){
  122.                             int k = (set.contains(trad(m,i-1,j)))?5:1;
  123.                             addEdge(graph, trad(m, i, j)+n*m,trad(m,i-1,j), k);
  124.                         }
  125.                         //Abajo
  126.                         if(i<n-1&&grid[i+1][j]!='#'){
  127.                             int k = (set.contains(trad(m,i+1,j)))?5:1;
  128.                             addEdge(graph, trad(m, i, j)+n*m,trad(m,i+1,j),k);
  129.                         }
  130.                         //Izquierda
  131.                         if(j>0&&grid[i][j-1]!='#'){
  132.                             int k = (set.contains(trad(m,i,j-1)))?5:1;
  133.                             addEdge(graph, trad(m, i, j)+n*m,trad(m,i,j-1), k);
  134.                         }
  135.                         //Derecha
  136.                         if(j<m-1&&grid[i][j+1]!='#'){
  137.                             int k = (set.contains(trad(m,i,j+1)))?5:1;
  138.                             addEdge(graph, trad(m, i, j)+n*m,trad(m,i,j+1), k);
  139.                         }
  140.                     }
  141.                 }
  142.             }
  143.             int sol = maxFlow(graph, trad(m, l.x, l.y), trad(m, c.x, c.y));
  144.             if(sol<=4){
  145.                 System.out.println(sol);
  146.             }
  147.             else{
  148.                 System.out.println("IMPOSIBLE");
  149.             }
  150.         }
  151.     }
  152. }
  153.  
Success #stdin #stdout 0.13s 49556KB
comments (?)
stdin
copy 
1
5 7
..#...#
...L...
...#...
..#....
.C....#
stdout
copy 
2
https://ideone.com/GbcgOa
language:
Java (HotSpot 12)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!