HDU3779(Railroad)

2014-11-24 10:39:56 · 作者: · 浏览: 1
[java]

import java.util.*;

public class Railroad {

static int[] arr1;
static int[] arr2;
static int[] arr;
static int n1, n2;
static boolean possible;
static boolean used[][];

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
n1 = sc.nextInt();
n2 = sc.nextInt();
if (n1 == 0 && n2 == 0)
break;

arr1 = new int[n1];
arr2 = new int[n2];
arr = new int[n1 + n2];
used = new boolean[n1+1][n2+1];
for(int i = 0;i<=n1;i++){
for(int j = 0;j<=n2;j++)
used[i][j] = false;
}
possible = false;

for (int i = 0; i < n1; i++)
arr1[i] = sc.nextInt();
for (int i = 0; i < n2; i++)
arr2[i] = sc.nextInt();
for (int i = 0; i < n1 + n2; i++)
arr[i] = sc.nextInt();

sove(0, 0, 0);
if (possible) www.2cto.com
System.out.println("possible");
else
System.out.println("not possible");
}

}

private static void sove(int i, int j, int k) {

if(used[i][j])return;

if (k == (n1 + n2)) {
possible = true;
return;
}

// System.out.println(i + "-" + j + "-" + k);

if (i < n1 && arr1[i] == arr[k])
sove(i + 1, j, k + 1);

if (j < n2 && arr2[j] == arr[k])
sove(i, j + 1, k + 1);

used[i][j] = true;
}

}