Archive for the ‘Depth first search’ Category

UVA – 11110 – Equidivisions   Leave a comment


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Equidivisions {
	public static int go(int i, int j, int src, int[][] arr) {
		if (i < 0 || j < 0 || i >= arr.length || j >= arr.length
				|| arr[i][j] == 0 || arr[i][j] != src)
			return 0;
		else {
			arr[i][j] = 0;
			return 1 + go(i + 1, j, src, arr) + go(i - 1, j, src, arr)
					+ go(i, j + 1, src, arr) + go(i, j - 1, src, arr);
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		while (true) {
			int n = Integer.parseInt(in.readLine());
			if (n == 0)
				break;
			int[][] arr = new int[n][n];
			for (int i = 0; i < arr.length; i++)
				Arrays.fill(arr[i], n);
			for (int i = 1; i <= n - 1; i++) {
				StringTokenizer strtok = new StringTokenizer(in.readLine(), " ");
				for (int j = 0; j < n; j++) {
					int a = Integer.parseInt(strtok.nextToken()) - 1;
					int b = Integer.parseInt(strtok.nextToken()) - 1;
					arr[a][b] = i;
				}
			}
			boolean flag = false;
			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++) {
					if (arr[i][j] != 0) {
						if (go(i, j, arr[i][j], arr) != n) {
							flag = true;
						}
					}
				}
			if (!flag)
				System.out.println("good");
			else
				System.out.println("wrong");

		}
	}

}

Posted May 18, 2012 by epicrado in Depth first search

UVA – 11709 – Trust groups   Leave a comment


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class TrustGroups {
	public static void dfs(int i, LinkedList<Integer>[] G, boolean[] v,
			Stack<Integer> sort) {
		if (!v[i]) {
			v[i] = true;
			for (int j : G[i])
				dfs(j, G, v, sort);
			sort.push(i);
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		while (true) {
			StringTokenizer st1 = new StringTokenizer(in.readLine(), " ");
			int p = Integer.parseInt(st1.nextToken());
			int t = Integer.parseInt(st1.nextToken());
			if (p == 0 && t == 0)
				break;
			TreeMap<String, Integer> map = new TreeMap<String, Integer>();
			LinkedList<Integer>[] G = new LinkedList[p];
			LinkedList<Integer>[] Gt = new LinkedList[p];
			for (int i = 0; i < p; i++) {
				map.put(in.readLine(), i);
				G[i] = new LinkedList<Integer>();
				Gt[i] = new LinkedList<Integer>();
			}
			for (int i = 0; i < t; i++) {
				int a = map.get(in.readLine());
				int b = map.get(in.readLine());
				G[a].add(b);
				Gt[b].add(a);
			}
			Stack<Integer> toposort = new Stack<Integer>();
			Stack<Integer> toposort2 = new Stack<Integer>();//reverse topological sort
			boolean[] vis = new boolean[p];
			for (int i = 0; i < p; i++)
				dfs(i, G, vis, toposort);
			int count = 0;
			boolean[] vis2 = new boolean[p];
			while (!toposort.isEmpty()) {
				int i = toposort.pop();
				if (!vis2[i]) {
					count++;
					dfs(i, Gt, vis2, toposort2);
				}
			}
			System.out.println(count);
		}
	}
}

Posted February 1, 2012 by epicrado in Depth first search

UVA – 11504 – Dominos   Leave a comment


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class dominoes {
	static LinkedList<Integer>[] G;
	static LinkedList<Integer>[] Gt;
	static LinkedList<pair> edges = new LinkedList<pair>();
	static int[] visited;
	static int[] finish;
	static int time;
	static int root;
	static int n;

	public static void dfs(int i, LinkedList<Integer>[] G) {
		if (visited[i] == 0) {
			visited[i] = root;
			for (int j : G[i])
				dfs(j, G);
			time++;
			finish[i] = time;
		}
	}

	public static int evaluate() {
		visited = new int[n + 1];
		finish = new int[n + 1];
		root = 0;
		time = 0;
		for (int i = 1; i <= n; i++) {
			if (visited[i] == 0) {
				root++;
				dfs(i, G);
			}
		}
		PriorityQueue<pair> q = new PriorityQueue<pair>();
		for (int i = 1; i <= n; i++) {
			q.add(new pair(i, finish[i]));
		}
		Arrays.fill(visited, 0);
		time = 0;
		root = 0;
		while (!q.isEmpty()) {
			pair p = q.remove();
			if (visited[p.s] == 0) {
				root++;
				dfs(p.s, Gt);
			}
		}
		boolean[] flag = new boolean[root + 1];
		for (pair p : edges) {
			if (visited[p.s] != visited[p.t]) {
				flag[visited[p.t]] = true;
			}
		}
		int count = 0;
		for (int i = 1; i <= root; i++)
			if (!flag[i])
				count++;
		return count;
	}

	public static class pair implements Comparable<pair> {
		int s, t;

		public pair(int s, int t) {
			this.s = s;
			this.t = t;
		}

		public String toString() {
			return s + " " + t;
		}

		@Override
		public int compareTo(pair arg0) {
			return arg0.t - t;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader bin = new BufferedReader(
				new InputStreamReader(System.in));
		int tc = Integer.parseInt(bin.readLine());
		StringBuilder out = new StringBuilder();
		while (tc-- > 0) {
			StringTokenizer st = new StringTokenizer(bin.readLine());
			edges.clear();
			n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			G = new LinkedList[n + 1];
			Gt = new LinkedList[n + 1];
			for (int i = 1; i <= n; i++) {
				G[i] = new LinkedList<Integer>();
				Gt[i] = new LinkedList<Integer>();
			}
			for (int i = 0; i < m; i++) {
				StringTokenizer st2 = new StringTokenizer(bin.readLine());
				int a = Integer.parseInt(st2.nextToken());
				int b = Integer.parseInt(st2.nextToken());
				G[a].add(b);
				Gt[b].add(a);
				edges.add(new pair(a, b));
			}
			out.append(evaluate() + "\n");
		}
		System.out.print(out);
	}
}

Posted January 24, 2012 by epicrado in Depth first search

UVA – 208 – Firetruck   1 comment


Regular backtracking but the idea here is to prune the branches which won’t lead us to the destination.

so simply run dfs from destination and mark all nodes that can lead us there.

And while backtracking if we’re a node that is not marked then we do nothing

import java.util.Scanner;

public class fire {
	static boolean[][] matrix;
	static boolean[] canVisit;
	static int counter;

	public static void dfs(int n, int max) {
		canVisit[n] = true;
		for (int i = 1; i <= max; i++)
			if (matrix[n][i] && !canVisit[i])
				dfs(i, max);
	}

	public static void generatePath(String path, int s, int e, int v, int max) {
		if (canVisit[s]) {
			if (s == e) {
				counter++;
				System.out.println(path);
			}
			for (int i = 1; i <= max; i++)
				if ((v & (1 << i)) == 0 && matrix[s][i])
					generatePath(path + " " + i, i, e, v | (1 << i), max);
		}
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int index = 1;
		while (in.hasNext()) {
			int n = in.nextInt();
			int max = 0;
			matrix = new boolean[22][22];
			canVisit = new boolean[22];
			counter = 0;
			int e1 = in.nextInt();
			int e2 = in.nextInt();
			while (e1 != 0 || e2 != 0) {
				matrix[e1][e2] = matrix[e2][e1] = true;
				e1 = in.nextInt();
				e2 = in.nextInt();
				max = Math.max(Math.max(e1, e2), max);
			}
			dfs(n, max);
			System.out.println("CASE " + (index++) + ":");
			generatePath("1", 1, n, 2, max);
			System.out
					.println("There are " + counter
							+ " routes from the firestation to streetcorner "
							+ n + ".");
		}
	}
}

Posted September 20, 2011 by epicrado in Depth first search, Recursive Backtracking

UVA – 776 – Monkeys in a Regular Forest   Leave a comment


#include <stdio.h>
#define max(a,b)(a>b)?a:b
char map[100][1000];
int res[100][1000];
char width[1000];
int dx[] = {0,0,1,-1,1,1,-1,-1};
int dy[] = {1,-1,0,0,1,-1,1,-1};
void solve(char src,int fill,int i,int j,int r,int c)
{
	if(i>=0&&j>=0&&i<r&&j<c&&map[i][j]==src&&!res[i][j])
	{
		int d;
		res[i][j]=fill;
		for(d=0;d<8;d++)
			solve(src,fill,i+dx[d],j+dy[d],r,c);
	}
}
int main()
{
	int i,j,top,max,l,m;
	char buffer[1000];
	char format[] = "%nd";
	top = 0;
	char done = 0;
	while(gets(buffer)&&!done)
	{
		if(buffer[0]=='%')
		{
			sol:
			max = 1;
			for(l=0;l<top;l++)
				for(m=0;m<j;m++)
					res[l][m]=0;
			for(l=0;l<top;l++)
				for(m=0;m<j;m++)
					if(!res[l][m])
						solve(map[l][m],max++,l,m,top,j);
			for(l=0;l<j;l++)
			{
				int max = 0;
				for(m=0;m<top;m++)
					max = max(max,res[m][l]);
				int places = 1;
				while(max>=10)
				{
					max/=10;
					places++;
				}
				width[l]=places+'0';
			}
			for(l=0;l<top;l++,putchar('\n'))
				for(m=0;m<j;m++)
				{
					format[1]=width[m];
					if(m)
						putchar(' ');
					printf(format,res[l][m]);
				}
			top = 0;
			putchar('%');
			putchar('\n');
			if(done)goto end;
		}
		else
		{
			j = 0;
			for(i=0;buffer[i];i++)
				if(buffer[i]!=' ')
					map[top][j++] = buffer[i];
			top++;
		}
	}
	done = 1;
	goto sol;
	end:return 0;
}

Posted August 27, 2011 by epicrado in Depth first search

UVA – 782 – Contour Painting   Leave a comment


Annoying input and output if you want to solve it watch out for thease

1.remove all trailing spaces from input

2.borders are not only ‘X’ but any other character than ‘_’,’*’,’#’ and space

#include <stdio.h>
#include <stdlib.h>
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
void visit(int i,int j,char** map)
{
	if(i>=0&&j>=0&&i<40&&j<100&&map[i][0]!='_'&&j<100&&(map[i][j]==' '||map[i][j]=='*'||!map[i][j]))
	{
		map[i][j]='#';
		visit(i+1,j,map);
		visit(i,j+1,map);
		visit(i-1,j,map);
		visit(i,j-1,map);
	}
}
int main()
{
	int c,i,j,top;
	char** temp =  (char**)malloc(40*sizeof(char*));
	char** map;
	map = (char**)malloc(40*sizeof(char*));
	for(i=0;i<40;i++)
	{
		map[i] = (char*) malloc(100);
		temp[i] =  (char*) malloc(100);
	}
	scanf("%d",&c);
	getchar();
	while(c-->0)
	{
			top=0;
			for(i=0;i<40;i++)
				for(j=0;j<100;j++)
					temp[i][j]=map[i][j]=0;
			while(gets(map[top])&&map[top][0]!='_')
			{
				i = 0;
				while(map[top][i])
					temp[top][i]=map[top][i++];
				top++;
			}
			i = 0;
			while(map[top][i])
				temp[top][i]=map[top][i++];
			top++;
			for(i=0;i<top;i++)
				for(j=0;map[i][j];j++)
					if(map[i][j]=='*')
					{
						visit(i,j,temp);
						map[i][j]=' ';
					}
			for(i=0;i<top;i++)
				for(j=0;j<100;j++)
					if(map[i][j]!='_'&&map[i][j]!=' '&&map[i][j]!='#'&&map[i][j])
					{
						int d;
						for(d=0;d<4;d++)
						{
							int cx = i + dx[d];
							int cy = j + dy[d];
							if(cx>=0&&cy>=0&&cx<40&&cy<100&&temp[cx][cy]=='#')
							{
								map[cx][cy]='#';
								int k;
								for(k=0;k<cy;k++)
									if(!map[cx][k])
										map[cx][k]=' ';
							}
						}
					}
			for(i=0;i<40;i++)
			{
				int max = -1;
				for(j=0;j<100;j++)
					if(map[i][j]&&map[i][j]!=' ')
						max = j;
				map[i][max+1]=0;
			}

			for(i=0;i<top;i++)
				printf("%s\n",map[i]);
		}
	return 0;
}

Posted August 22, 2011 by epicrado in Depth first search

UVA – 784 – Maze Exploration   Leave a comment




#include <stdio.h>
#include <stdlib.h>
void visit(int i,int j,char** map)
{
	if(map[i][j]==' '||map[i][j]=='*')
	{
		map[i][j]='#';
		visit(i+1,j,map);
		visit(i,j+1,map);
		visit(i-1,j,map);
		visit(i,j-1,map);
	}
}
int main()
{
	int c,i,j,k,top;
	char** map;
	map = (char**)malloc(40*sizeof(char*));
	for(i=0;i<40;i++)
		map[i] = (char*) malloc(100);
	scanf("%d\n",&c);
	while(c-->0)
	{
		top=0;
		while(gets(map[top])&&map[top++][0]!='_');
		for(i=0;i<100;i++)
			map[top][i]=0;
		for(i=0;map[i][0]!='_';i++)
		{
			for(j=0;map[i][j];j++)
			{
				if(map[i][j]=='*')
				{
					visit(i,j,map);
				}
			}
		}
		for(i=0;map[i][0];i++)
		{
			puts(map[i]);
		}
	}
	return 0;
}

Posted August 21, 2011 by epicrado in Depth first search