Archive for the ‘Breadth first search’ Category

UVA – 12274 – Jumping monkey   Leave a comment


#include <stdio.h>
int q[1<<22];
int lg2[1<<22];
int g[22];
char v[1<<21];
int next[1<<21];
int parent[1<<21];
int choice[1<<21];
int out[1001];
int h,t;
int isEmpty()
{
	return (t-h+(1<<22))%(1<<22)==0;
}
void enq(int n)
{
	q[t]=n;
	t=(t+1)%(1<<22);
}
void clear()
{
	h = t = 0;
}
int deq()
{
	int res = q[h];
	h = (h+1)%(1<<22);
	return res;
}
int main()
{
	int n,m,i,j,k,l;
	for(i=0;i<22;i++)
		lg2[1<<i]=i;
	while(1)
	{
		scanf("%d %d",&n,&m);
		
		if(!n&&!m)break;
		
		for(i = 0;i<n;i++)g[i]=0;
		
		for(i = 0;i<m;i++)
		{
			scanf("%d %d",&k,&l);
			g[k]|=(1<<l);
			g[l]|=(1<<k);
		}
		
		for(i = 0;i<1<<n;i++)
			next[i]=v[i]=0;
		
		for(i = 1;i<1<<n;i++)
			next[i]=next[i-(i&-i)]|g[lg2[i&-i]];
		
		clear();
		
		enq((1<<n)-1);
		v[(1<<n)-1]=1;
		int f = 0;
		while(!isEmpty())
		{
			int current = deq();
			if(!current)
			{
				int top = 0;
				while(current!=(1<<n)-1)
				{
					out[top++]=choice[current];
					current = parent[current];
				}
				printf("%d:",top);
				--top;
				while(top>=0)
					printf(" %d",out[top--]);
				putchar('\n');
				f = 1;
				break;
			}
			int mask = current;
			while(mask!=0)
			{
				int nx = next[current^(mask&-mask)];
				if(!v[nx])
				{
					v[nx]=1;
					enq(nx);
					parent[nx]=current;
					choice[nx]=lg2[(mask&-mask)];
				}
				mask-=mask&-mask;
			}
		}
		if(!f)
			puts("Impossible");
	}
	return 0;
}

Posted July 29, 2012 by epicrado in Breadth first search, Dynamic programming

UVA – 10959 – The Party, Part I   Leave a comment


Direct bfs start at Don Giovanni (node 0) and record shortest path to all other nodes

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

public class TheParty {

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		int tc = in.nextInt();
		while (tc-- > 0) {
			int n = in.nextInt();
			int m = in.nextInt();
			boolean[][] g = new boolean[n][m];
			for (int i = 0; i < m; i++) {
				int a = in.nextInt();
				int b = in.nextInt();
				g[a][b] = g[b][a] = true;
			}

			int[] dist = new int[n];
			Arrays.fill(dist, -1);
			dist[0] = 0;
			Queue<Integer> Q = new ArrayDeque<Integer>();
			Q.add(0);
			while (!Q.isEmpty()) {
				int i = Q.remove();
				for (int j = 0; j < n; j++)
					if (g[i][j] && dist[j] == -1) {
						dist[j] = dist[i] + 1;
						Q.add(j);
					}
			}
			for (int i = 1; i < n; i++)
				System.out.println(dist[i]);
			if (tc != 0)
				System.out.println();
		}
	}

	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

Posted June 23, 2012 by epicrado in Breadth first search

UVA – 11405 – Can U Win?   Leave a comment


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class CanUWin {
	static int[] dik = { 1, -1, 1, -1, 2, 2, -2, -2 };
	static int[] djk = { 2, 2, -2, -2, 1, -1, 1, -1 };

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(in.readLine());
		while (tc-- > 0) {
			String s = in.readLine();
			while (s.length() == 0)
				s = in.readLine();
			int n = Integer.parseInt(s);
			char[][] map = new char[8][];
			for (int i = 0; i < map.length; i++)
				map[i] = in.readLine().toCharArray();

			int[][] bitIndex = new int[8][8];
			int top = 0;
			int xk = 0;
			int yk = 0;
			for (int i = 0; i < map.length; i++)
				for (int j = 0; j < map[i].length; j++)
					bitIndex[i][j] = -1;
			for (int i = 0; i < map.length; i++)
				for (int j = 0; j < map[i].length; j++) {
					if (map[i][j] == 'P')
						bitIndex[i][j] = top++;
					else if (map[i][j] == 'k') {
						xk = i;
						yk = j;
					}
				}
			long[] vis = new long[1 << top];
			int loc = xk * 8 + yk;
			vis[0] |= (1L << loc);
			Queue<Integer> Q = new LinkedList<Integer>();
			Q.add(loc);
			Q.add(0);
			Q.add(0);
			boolean flag = false;
			while (!Q.isEmpty()) {

				int kloc = Q.poll();
				int mask = Q.poll();
				int steps = Q.poll();
				if (mask == (1 << top) - 1) {
					flag = true;
					break;
				}
				if (steps < n) {
					int ki = kloc / 8;
					int kj = kloc % 8;
					for (int i = 0; i < dik.length; i++) {
						int nki = ki + dik[i];
						int nkj = kj + djk[i];
						if (nki < 8
								&& nkj < 8
								&& nki >= 0
								&& nkj >= 0
								&& (map[nki][nkj] == '.'
										|| map[nki][nkj] == 'P' || map[nki][nkj] == 'k')) {
							int newloc = nki * 8 + nkj;
							int newmask = mask;
							if (bitIndex[nki][nkj] != -1)
								newmask |= (1 << bitIndex[nki][nkj]);
							if ((vis[newmask] & (1L << newloc)) == 0) {
								vis[newmask] |= 1L << newloc;
								Q.add(newloc);
								Q.add(newmask);
								Q.add(steps + 1);
							}
						}
					}
				}
			}
			if (flag)
				System.out.println("Yes");
			else
				System.out.println("No");

		}
	}
}

Posted February 5, 2012 by epicrado in Breadth first search, Graphs

UVA – 12160 – Unlock the Lock   Leave a comment


import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class UnlockTheLock {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int cc = 1;
		int s = in.nextInt(), d = in.nextInt(), m = in.nextInt();
		while (s != 0 || d != 0 || m != 0) {
			boolean[] V = new boolean[10000];
			int[] add = new int[m];
			for (int i = 0; i < m; i++)
				add[i] = in.nextInt();
			Queue<Integer> Q = new LinkedList<Integer>();
			V[s] = true;
			Q.add(s);
			Q.add(0);
			boolean found = false;
			while (!Q.isEmpty()) {
				int current = Q.remove();
				int len = Q.remove();
				if (current == d) {
					found = true;
					System.out.printf("Case %d: %d\n", cc++, len);
					break;
				}
				for (int i = 0; i < m; i++) {
					int currentstate = (current + add[i]) % 10000;
					if (!V[currentstate]) {
						Q.add(currentstate);
						Q.add(len + 1);
						V[currentstate] = true;
					}
				}
			}
			if (!found)
				System.out.printf("Case %d: Permanently Locked\n", cc++);
			s = in.nextInt();
			d = in.nextInt();
			m = in.nextInt();
		}
	}
}

Posted September 30, 2011 by epicrado in Breadth first search

UVA – 571 – Jugs   Leave a comment


import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Jugs {
	static String[] res = { "fill A", "fill B", "empty A", "empty B",
			"pour A B", "pour B A", "success" };
	static int[][] pi = new int[1005][1005];
	static int[][] pj = new int[1005][1005];
	static byte[][] step = new byte[1005][1005];
	static boolean[][] v = new boolean[1005][1005];

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int ca = in.nextInt(), cb = in.nextInt(), n = in.nextInt();
			int max = Math.max(ca, Math.max(cb, n));
			for (int i = 0; i <= max; i++)
				for (int j = 0; j <= max; j++) {
					v[i][j] = false;
					pi[i][j] = i;
					pj[i][j] = j;
				}
			Queue<Integer> Q = new LinkedList<Integer>();
			Q.add(0);
			Q.add(0);
			v[0][0] = true;
			int a = 0, b = 0;
			v[0][0] = true;
			while (!Q.isEmpty()) {
				a = Q.remove();
				b = Q.remove();
				if (b == n)
					break;
				if (!v[ca][b]) {
					Q.add(ca);
					Q.add(b);
					pi[ca][b] = a;
					pj[ca][b] = b;
					v[ca][b] = true;
					step[ca][b] = 0;
				}
				if (!v[a][cb]) {
					Q.add(a);
					Q.add(cb);
					pi[a][cb] = a;
					pj[a][cb] = b;
					v[a][cb] = true;
					step[a][cb] = 1;
				}
				if (!v[0][b]) {
					Q.add(0);
					Q.add(b);
					pi[0][b] = a;
					pj[0][b] = b;
					v[0][b] = true;
					step[0][b] = 2;
				}
				if (!v[a][0]) {
					Q.add(a);
					Q.add(0);
					pi[a][0] = a;
					pj[a][0] = b;
					v[a][0] = true;
					step[a][0] = 3;
				}
				int x = Math.min(a, cb - b);
				int y = Math.min(b, ca - a);
				if (!v[a - x][b + x]) {
					Q.add(a - x);
					Q.add(b + x);
					pi[a - x][b + x] = a;
					pj[a - x][b + x] = b;
					v[a - x][b + x] = true;
					step[a - x][b + x] = 4;
				}
				if (!v[a + y][b - y]) {
					Q.add(a + y);
					Q.add(b - y);
					pi[a + y][b - y] = a;
					pj[a + y][b - y] = b;
					v[a + y][b - y] = true;
					step[a + y][b - y] = 5;
				}

			}
			LinkedList<Byte> L = new LinkedList<Byte>();
			while (pi[a][b] != a || pj[a][b] != b) {
				L.push(step[a][b]);
				int x = pi[a][b];
				int y = pj[a][b];
				a = x;
				b = y;
			}
			for (Byte i : L)
				System.out.println(res[i]);
			System.out.println("success");
		}
	}
}

Posted September 22, 2011 by epicrado in Breadth first search

UVA – 10856 – Recover Factorial   1 comment


#include <stdio.h>
#define N 2703664
int factors[N];
int main()
{
	int i,j,k,mid,c=1;
	for(i=0;i<N;i++)
		factors[i]=0;
	for(i=2;i<N;i++)
	{
		if(!factors[i])
			factors[i]=1;
		for(j=2;(k=i*j)<N&&j<=i;j++)
			if(factors[j]==1)
				factors[k]=factors[j]+factors[i];
	}
	for(i=2;i<N;i++)
		factors[i]+=factors[i-1];
	scanf("%d",&k);
	while(k>=0)
	{
		i = 0;
		j = 2703663;
		while(j-i>1)
		{
			mid = (j+i)/2;
			if(factors[mid]<k)
				i = mid;
			else
				j = mid;
		}
		if(factors[i]==k)
			printf("Case %d: %d!\n",c++,i);
		else if(factors[j]==k)
			printf("Case %d: %d!\n",c++,j);
		else
			printf("Case %d: Not possible.\n",c++);
		scanf("%d",&k);
	}
	return 0;
}

Posted September 1, 2011 by epicrado in Breadth first search, Factorials, Prime numbers

UVA – 11352 – Crazy King   Leave a comment


Take care : if a knight can reach a place in ONE move then the king can't go there ,
this problem is a little like 11624 - Fire But this one is easier

#include <queue>
#include <stdio.h>
using namespace std;
char map[105][105];
int steps[105][105];
int dxk[] = {1,-1,1,-1,2,2,-2,-2};
int dyk[] = {2,2,-2,-2,1,-1,1,-1};
int dx[] ={0,0,1,-1,1,-1,1,-1};
int dy[] ={1,-1,0,0,1,-1,-1,1};
int main()
{
	int r,c,runs;
	scanf("%d",&runs);
	while(runs--)
	{
		scanf("%d %d",&r,&c);
		getchar();
		int si,sj,ei,ej;
		for(int i=0;i<r;i++)
			gets(map[i]);
		queue<int> Q;
		for(int i=0;i<r;i++)
		{
			for(int j =0;j<c;j++)
			{
				steps[i][j]=-1;
				if(map[i][j]=='Z')
				{
					steps[i][j]=0;
					Q.push(i);
					Q.push(j);
					Q.push(0);
				}
				else if(map[i][j]=='A')
				{
					si = i;
					sj = j;
				}
				else if(map[i][j]=='B')
				{
					ei = i;
					ej = j;
				}
			}
		}
		while(Q.size())
		{
			int i = Q.front();Q.pop();
			int j = Q.front();Q.pop();
			int t = Q.front();Q.pop();
			for(int d = 0;d<8;d++)
			{
					int x = i + dxk[d];
					int y = j + dyk[d];
					if(x>=0&&x<r&&y>=0&&y<c&&map[x][y]=='.'&&steps[x][y]==-1&&!t)
					{
						steps[x][y]=t+1;
						Q.push(x);Q.push(y);Q.push(t+1);
					}
			}
		}
		bool found = false;
		Q.push(si);
		Q.push(sj);
		Q.push(0);
		map[si][sj]='V';
		while(Q.size()&&!found)
		{
			int ci = Q.front();Q.pop();
			int cj = Q.front();Q.pop();
			int t = Q.front();Q.pop();
			if(ci==ei&&cj==ej)
			{
				printf("Minimal possible length of a trip is %d\n",t);
				found = true;
			}
			else for(int d = 0;d<8;d++)
			{
				int x = ci + dx[d];
				int y = cj + dy[d];
				if(x>=0&&y>=0&&x<r&&y<c&&map[x][y]!='V'&&(steps[x][y]==-1||t+1<steps[x][y]))
				{
					map[x][y]='V';
					Q.push(x);
					Q.push(y);
					Q.push(t+1);
				}
			}
		}
		if(!found)
			puts("King Peter, you can't go now!");
	}
}

Posted August 27, 2011 by epicrado in Breadth first search