D2008
unknown
plain_text
21 days ago
9.7 kB
1
Indexable
Never
/////////////////////////////////
package d2008;
import java.util.Scanner;
public class MoiDamCuoi {
static int t,n,m,u,v;
static int[][] a = new int[n+1][n+1];
static int[] visit = new int[n+1];
static class Queue{
int front,rear;
int[] data = new int[90001];
public Queue(){
front = rear = 0;
}
public void enQ(int n){
data[rear++] = n;
}
public int deQ(){
return data[front++];
}
public int qPeek(){
return data[front];
}
public boolean isEmpty(){
if(front == rear){
return true;
}
return false;
}
}
public static boolean BFS(int u, int v){
Queue q = new Queue();
q.enQ(u);
visit[u] = 1;
while(!q.isEmpty()){
int nx = q.deQ();
for(int i = 1 ; i <= n ; i++){
if(a[nx][i] == 1 && visit[i] == 0 ){
visit[i] = 1;
q.enQ(i);
}
}
if(nx == v){
return true;
}
}
return false;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
for(int tc = 1 ; tc <= t ; tc++){
n = sc.nextInt();
m = sc.nextInt();
u = sc.nextInt();
v = sc.nextInt();
a = new int[n+1][n+1];
visit = new int[n+1];
for(int i = 0 ; i < m ; i++){
int x = sc.nextInt();
int y = sc.nextInt();
a[x][y] = 1;
}
int res = 0;
for(int i = 1 ; i <= n ; i++){
if(i == u || i == v){
continue;
}
visit = new int[n+1];
visit[i] = 1;
if(!BFS(u, v)){
res++;
}
}
System.out.println(res);
System.out.println();
}
}
}
//////////////////
package d2008;
import java.util.Scanner;
public class DiAnCuoi {
static int t,n,m;
static int[][] a = new int[n+1][n+1];
static int[] visit = new int[n+1];
static int res = 99999999;
public static void Try(int k,int cnt){
if(cnt > res ){
return;
}
if(visit[1]==2){
if(visit[2] == 1){
res = Math.min(res, cnt);
}
return;
}
for(int i = 1 ; i <= n ; i++){
if(a[k][i] == 1){
if(visit[i] == 0){
visit[i] = 1;
Try(i, cnt+1);
visit[i] =0;
}
if(visit[i] == 1){
visit[i]++;
Try(i, cnt);
visit[i]--;
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
for(int tc = 1 ; tc <= t; tc++){
n = sc.nextInt();
m = sc.nextInt();
a = new int[n+1][n+1];
visit = new int[n+1];
for(int i = 0 ; i < m ; i++){
int x = sc.nextInt();
int y = sc.nextInt();
a[x][y] = 1;
}
res = 99999999;
visit[1]=1;
Try(1, 1);
System.out.println(res);
}
}
}
////////////////////////////
package d2008;
import java.util.Scanner;
public class HugoGiaoHang {
static int t,sx,sy,hx,hy,n;
static int[][] a = new int[n+1][2];
static boolean[] visit = new boolean[n+1];
public static int cal(int x1,int y1,int x2,int y2){
return Math.abs(x1-x2)+Math.abs(y1-y2);
}
static int res = 99999999;
public static void Try(int k,int cnt,int prev){
if(k == n+1){
int tmp = cal(hx, hy, a[prev][0], a[prev][1]);
if(res > cnt + tmp){
res = cnt +tmp;
}
}
if(cnt > res){
return;
}
for(int i = 1 ; i <= n ; i++){
if(visit[i] == false){
visit[i] = true;
int tmp = cal(a[prev][0], a[prev][1], a[i][0], a[i][1]);
Try(k+1, cnt+tmp, i);
visit[i] = false;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
for(int tc = 1 ; tc <= t ; tc++){
sx = sc.nextInt();
sy = sc.nextInt();
hx = sc.nextInt();
hy = sc.nextInt();
n = sc.nextInt();
a = new int[n+1][2];
a[0][0]= sx;
a[0][1]= sy;
visit = new boolean[n+1];
for(int i = 1 ; i <= n ; i++){
a[i][0] = sc.nextInt();
a[i][1] = sc.nextInt();
}
res = 99999999;
Try(1, 0, 0);
System.out.println("Case #"+tc+" " +res);
}
}
}
//////////////////////////
package d2008;
import java.util.Scanner;
public class HugoDaoVangLevel4 {
static int t, n, g;
static int[][] a = new int[n][n];
static int[][] movang = new int[g][2];
static int res = 9999999;
static int[][] visit = new int[n][n];
static int[][] step = { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };
static class Queue {
int front, rear;
int[] data = new int[90001];
public Queue() {
front = rear = 0;
}
public void enQ(int n) {
data[rear++] = n;
}
public int deQ() {
return data[front++];
}
public int qPeek() {
return data[front];
}
public boolean isEmpty() {
if (front == rear) {
return true;
}
return false;
}
}
public static boolean checkMoVang(int r, int c) {
for (int i = 0; i < g; i++) {
if (movang[i][0] == r + 1 && movang[i][1] == c + 1) {
return true;
}
}
return false;
}
public static int solve() {
int cnt = 0;
for (int i = 0; i < g; i++) {
if (visit[movang[i][0] - 1][movang[i][1] - 1] > cnt) {
cnt = visit[movang[i][0] - 1][movang[i][1] - 1];
}
}
return cnt;
}
public static void BFS(int r, int c) {
Queue qx = new Queue();
Queue qy = new Queue();
qx.enQ(r);
qy.enQ(c);
visit[r][c] = 1;
while (!qx.isEmpty() && !qy.isEmpty()) {
int nx = qx.deQ();
int ny = qy.deQ();
for (int i = 0; i < 4; i++) {
int tmpx = nx + step[i][0];
int tmpy = ny + step[i][1];
if (tmpx >= 0 && tmpx < n && tmpy >= 0 && tmpy < n
&& visit[tmpx][tmpy] == 0 && a[tmpx][tmpy] == 1) {
visit[tmpx][tmpy] = visit[nx][ny] + 1;
qx.enQ(tmpx);
qy.enQ(tmpy);
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
for (int tc = 1; tc <= t; tc++) {
n = sc.nextInt();
g = sc.nextInt();
a = new int[n][n];
movang = new int[g][2];
visit = new int[n][n];
for (int i = 0; i < g; i++) {
movang[i][0] = sc.nextInt();
movang[i][1] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = sc.nextInt();
}
}
res = 9999999;
int x = -1, y = -1;
int dem = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 1 && !checkMoVang(i, j)) {
visit = new int[n][n];
BFS(i, j);
int tmp = solve();
int dem1 = 0;
for (int k = 0; k < g; k++) {
if (visit[movang[k][0] - 1][movang[k][1] - 1] != 0) {
dem1++;
}
}
if(dem1 == dem){
if(res > tmp && tmp!=0){
res = tmp;
x = i;
y = j;
}
}
else if(dem1 > dem){
dem = dem1;
res = tmp;
x = i;
y = j;
}
}
}
}
System.out.println("Case #" + tc);
if (res == 9999999) {
System.out.println(-1);
} else {
System.out.println(res-1);
visit = new int[n][n];
BFS(x, y);
for (int i = 0; i < g; i++) {
if (visit[movang[i][0] - 1][movang[i][1] - 1] == 0) {
System.out.println(movang[i][0] + " " + movang[i][1]);
}
}
}
}
}
}
/////////////////////////////
package d2008;
import java.util.Scanner;
public class HugoDaoVang {
static int t,n,g;
static int[][] a = new int[n][n];
static int[][] movang = new int[g][2];
static int res = 9999999;
static int[][] visit = new int[n][n];
static int[][] step = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
static class Queue{
int front,rear;
int[] data = new int[90001];
public Queue(){
front = rear = 0;
}
public void enQ(int n){
data[rear++] = n;
}
public int deQ(){
return data[front++];
}
public int qPeek(){
return data[front];
}
public boolean isEmpty(){
if(front == rear){
return true;
}
return false;
}
}
public static boolean checkMoVang(int r,int c){
for(int i = 0 ; i < g ; i++){
if(movang[i][0] == r+1 && movang[i][1] == c+1){
return true;
}
}
return false;
}
public static int solve(){
int cnt = 0;
int dem = 0;
for(int i = 0 ; i < g ; i++){
if(visit[movang[i][0]-1][movang[i][1]-1] > cnt ){
cnt = visit[movang[i][0]-1][movang[i][1]-1];
}
if(visit[movang[i][0]-1][movang[i][1]-1] != 0){
dem++;
}
}
if(dem == g){
return cnt;
}
return 0;
}
public static void BFS(int r,int c){
Queue qx = new Queue();
Queue qy = new Queue();
qx.enQ(r);
qy.enQ(c);
visit[r][c] = 0;
while(!qx.isEmpty() && !qy.isEmpty()){
int nx = qx.deQ();
int ny = qy.deQ();
for(int i = 0 ; i < 4 ; i++){
int tmpx = nx + step[i][0];
int tmpy = ny + step[i][1];
if(tmpx >= 0 && tmpx < n && tmpy >= 0 && tmpy < n && visit[tmpx][tmpy] == 0 && a[tmpx][tmpy] == 1){
visit[tmpx][tmpy] = visit[nx][ny]+1;
qx.enQ(tmpx);
qy.enQ(tmpy);
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
t = sc.nextInt();
for(int tc = 1 ; tc <= t ; tc++){
n = sc.nextInt();
g = sc.nextInt();
a = new int[n][n];
movang = new int[g][2];
visit = new int[n][n];
for(int i = 0 ; i < g ; i++){
movang[i][0] = sc.nextInt();
movang[i][1] = sc.nextInt();
}
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++){
a[i][j] = sc.nextInt();
}
}
res = 9999999;
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++){
if(a[i][j] == 1 && !checkMoVang(i, j)){
visit = new int[n][n];
BFS(i, j);
int tmp = solve();
if(res > tmp && tmp!=0){
res = tmp;
}
}
}
}
System.out.println("Case #"+tc);
if(res == 9999999){
System.out.println(-1);
}
else{
System.out.println(res);
}
}
}
}
Leave a Comment