uva: 11831 Sticker Collector Robots

Problem and solution analysis: it is simple graph traversal problem.


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


 class Main_11831_StickerCollectorRobots {

	/**
	 * TL
	 * Graph Traversal
	 * http://uva.onlinejudge.org/external/118/11831.html
	 * 
	 * `.' -- normal cell;
`*' -- cell which contains a sticker;
`#' -- cell which contains a pillar;
`N' - North, `S' - South, `L' - EAST, `O' - West -- cell where the robot starts the rally

D -``turn 90 degrees to the right"
E- ``turn 90 degrees to the left" 
F - ``move forward one cell"
	 */
	
	
	private  static  final char RIGHT='D',LEFT='E', MOVE='F';
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String dirs = "NLSO";//NESW
		int[] dr = {-1,0,1, 0};//NESW
		int[] dc = { 0,1,0,-1};//		
		char[][] graph;
		int NRow, MCol, SIns, stickerCount, index;
		int currentDir, currentRow, currentCol, newr, newc;		
		String instruction;
		String[] strArray;
		char ch;
		

		while(true)
		{
			strArray = br.readLine().trim().split(" ");
			
			NRow = Integer.parseInt(strArray[0]);
			if(NRow == 0) break;

			MCol = Integer.parseInt(strArray[1]);
			SIns = Integer.parseInt(strArray[2]);			
			currentRow = 0;
			currentCol =0;
			currentDir = 0;
			graph = new char[NRow][MCol];
			
			for(int i=0; i < NRow; i++)
			{				
				graph[i] = br.readLine().trim().toCharArray();

				for(int j=0; j < MCol; j++)
				{					
					index = dirs.indexOf(graph[i][j]);
					if(index>=0)
					{						
						currentDir = index;
						currentRow = i;
						currentCol = j;							
					}
				}
			}

			instruction = br.readLine().trim();
			stickerCount = 0;
			for(int i=0; i < SIns; i++)
			{
				ch = instruction.charAt(i);
				if(ch==RIGHT )
					currentDir= (currentDir + 1) % 4;
				else if(ch == LEFT)
					currentDir= (currentDir + 3) % 4;
				else if(ch == MOVE)
				{
					newr = currentRow +  dr[currentDir];
					newc = currentCol + dc[currentDir];
					if(newr>=0 && newc>=0 && newr < NRow && newc < MCol && graph[newr][newc] != '#')
					{						
						if(graph[newr][newc]=='*')
						{
							stickerCount++;
							graph[newr][newc] = '.';							
						}
						currentRow = newr;
						currentCol = newc;
					}
				}
			}
			
			System.out.println(stickerCount);
		}
	}
}

/*

 Sample Input 

3 3 2
***
*N*
***
DE
4 4 5
...#
*#O.
*.*.
*.#.
FFEFF
10 10 20
....*.....
.......*..
.....*....
..*.#.....
...#N.*..*
...*......
..........
..........
..........
..........
FDFFFFFFEEFFFFFFEFDF
0 0 0

Sample Output 

0
1
3


 * */


Advertisements

About M Moniruzzaman
A passionate software engineer, have been developing applications on various platforms such as Android, iPhone, .Net (C#) technologies and web based ASP.NET, PHP, JavaScript, jQuery technologies for more than 10 years. Especially I have expertise on developing applications for Android and iPhone, as well as service oriented, client-server based applications where clients will be reside on Android/iPhone that communicate with WCF(.NET) service hosted on server. I have completed certification in Microsoft Certified Professional Developer (MCPD) on .Net 4 . I have completed my graduation in -- B.Sc. (Engineering) in Computer Science and Engineering, ShahJalal University of Science and Technology, Bangladesh. Thanks, M. Moniruzzaman (Zaman)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: