Source Code

Problem: 1071  User: yzhw 
Memory: 1540K  Time: 2110MS 
Language: Java  Result: Accepted 

Source Code 
import java.io.*;
import java.util.*;
class path
{
	//左 0，右 1，上 2，下 3
	int start,end,de;
	char c;
	void reserve()
	{
		switch(c)
		{
		case 'R':de=0;break;
		case 'L':de=1;break;
		case 'U':de=3;break;
		case 'D':de=2;break;
		};
	}
};
public class Main {

	static int[][][] data;
	static boolean[][] temp,used;
	static int r,c,total;
	static ArrayList list=new ArrayList();
	static int cul(int i,int j,int l)
	{
		
		if(i<1||i>r||j<1||j>c||temp[i][j]==true) return -1;
		else if(data[i][j][l]!=-2) return data[i][j][l];
		else
		{
			switch(l)
			{
			case 0:data[i][j][l]=cul(i,j-1,l)+1;break;
			case 1:data[i][j][l]=cul(i,j+1,l)+1;break;
			case 2:data[i][j][l]=cul(i-1,j,l)+1;break;
			case 3:data[i][j][l]=cul(i+1,j,l)+1;break;
			};
			return data[i][j][l];
		}
	}
	static void det(int i,int j,int num)
	{
		if(num==-1)
		{
			if(!used[i][j])
			{
				used[i][j]=true;
				total++;
			}
			return;
		}
		else
		{
			path t=(path)list.get(num);
			for(int k=t.start;k<=Math.min(data[i][j][t.de], t.end);k++)
			{
				switch(t.de)
				{
				case 0:det(i,j-k,num-1);break;
				case 1:det(i,j+k,num-1);break;
				case 2:det(i-k,j,num-1);break;
				case 3:det(i+k,j,num-1);break;
				};
			}
		}
	}
	public static void main(String[] args) throws IOException{
		StreamTokenizer in=new StreamTokenizer(System.in);
		int test;
		in.nextToken();
		test=(int)in.nval;
		for(int i=1;i<=test;i++)
		{
			list.clear();
			total=0;
			in.nextToken();
		   r=(int)in.nval;
		   in.nextToken();
		   c=(int)in.nval;
		   temp=new boolean[r+1][c+1];
		   used=new boolean[r+1][c+1];
		   data=new int[r+1][c+1][4];
		   for(int j=1;j<=r;j++)
			   for(int k=1;k<=c;k++)
			   {
				   in.nextToken();
				   if((int)in.nval==1) 
					   {
					    temp[j][k]=true;
					    data[j][k][0]=data[j][k][1]=data[j][k][2]=data[j][k][3]=-1;
					    
					   }
				   else 
				      {   
				    	temp[j][k]=false;
				    	data[j][k][0]=data[j][k][1]=data[j][k][2]=data[j][k][3]=-2;
				      }
				   used[j][k]=false;
			   }
		   while(true)
		   {
			   path t=new path();
			   in.nextToken();
			   t.start=(int)in.nval;
			   in.nextToken();
			   t.end=(int)in.nval;
			   if(t.start==0&&t.end==0) break;
			   in.nextToken();
			   t.c=in.sval.charAt(0);
			   list.add(t);
		   }
		   for(int j=0;j<list.size();j++) ((path)list.get(j)).reserve();
		   for(int j=1;j<=r;j++)
			   for(int k=1;k<=c;k++)
				   for(int l=0;l<4;l++)
				   {
					   if(data[j][k][l]==-2)
					   {
						   data[j][k][l]=cul(j,k,l);
						   
					   }
				//   System.out.println(j+" "+k+" "+l+"="+data[j][k][l]);
				   }
		   
			for(int j=1;j<=r;j++)	
				for(int k=1;k<=c;k++)
					if(!temp[j][k])
				     {
						
						det(j,k,list.size()-1);
						
				     }
	
			System.out.println(total);
		}
		
        
	}

}