fork(1) download
copy 
  1. import java.io.*;
  2. import java.math.BigInteger;
  3. import java.util.*;
  4.  
  5.  
  6. public class Main{
  7. 	public static final int mod = 1000003;
  8. 	public static int r,c,s,dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
  9. 	public static double a,b,ans;
  10. 	public static boolean ap[][];
  11. 	public static double visited[][][];
  12. 	public static void main(String[] args)throws IOException {
  13. 		// TODO Auto-generated method stub
  14. 		InputStream input = System.in;
  15.  
  16.  
  17. 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  18.  
  19. 		Reader in = new Reader();
  20.  
  21. 		int t = Integer.parseInt(br.readLine());
  22.  
  23. 		for(int o=1; o<=t; o++)
  24. 		{
  25. 			StringTokenizer st = new StringTokenizer(br.readLine());
  26.  
  27. 			 r = Integer.parseInt(st.nextToken());
  28. 			 c = Integer.parseInt(st.nextToken());
  29. 			int rs = Integer.parseInt(st.nextToken());
  30. 			int cs = Integer.parseInt(st.nextToken());
  31. 			 s = Integer.parseInt(st.nextToken());
  32.  
  33. 			st = new StringTokenizer(br.readLine());
  34.  
  35. 			 a = Double.parseDouble(st.nextToken());
  36. 			 b = Double.parseDouble(st.nextToken());
  37.  
  38. 			 ap = new boolean[r][c];
  39.  
  40. 			for(int i=0; i<r; i++)
  41. 			{
  42. 				st = new StringTokenizer(br.readLine());
  43. 				for(int j=0; j<c; j++)
  44. 					if(st.nextToken().equals("A"))
  45. 						ap[i][j] = true;
  46. 			}
  47.  
  48. 			visited = new double[r][c][s+1];
  49.  
  50. 			ans = -1;
  51.  
  52. 				int tt[][] = new int[r][c];
  53. 				dfs(rs,cs,0,0,tt);
  54.  
  55.  
  56.  
  57.  
  58. 			System.out.println("Case #"+o+": "+ans);
  59. 		}
  60. 	}
  61.  
  62. 	static void dfs(int x,int y,double p, int steps,int t[][])
  63. 	{	
  64. 		if(steps == s)
  65. 		{
  66. 			ans = Math.max(ans,p);
  67. 			return;
  68. 		}
  69.  
  70. 		for(int i=0; i<4; i++)
  71. 		{
  72. 			int xx = x+dx[i];
  73. 			int yy = y+dy[i];
  74.  
  75. 			if(xx<0 || xx >=r || yy<0 || yy>=c)
  76. 				continue;
  77. 			double pt = -1;
  78.  
  79. 			if(t[xx][yy] != 0)
  80. 				pt = p + (ap[xx][yy]?a:b)*Math.pow(ap[xx][yy]?(1-a):(1-b),t[xx][yy]);
  81. 			else
  82. 				pt = p + (ap[xx][yy]?a:b);
  83.  
  84. 			if(visited[xx][yy][steps+1] <= pt)
  85. 			{
  86. 				visited[xx][yy][steps+1] = pt;
  87. 				t[xx][yy]++;
  88.  
  89.  
  90. 				dfs(xx,yy,pt,steps+1,t);
  91. 				t[xx][yy]--;
  92. 			}
  93.  
  94.  
  95. 		}
  96.  
  97.  
  98.  
  99.  
  100. 	}
  101.  
  102.  
  103.  
  104.  
  105. 	 static class Reader
  106. 	    {
  107. 	        final private int BUFFER_SIZE = 1 << 16;
  108. 	        private DataInputStream din;
  109. 	        private byte[] buffer;
  110. 	        private int bufferPointer, bytesRead;
  111.  
  112. 	        public Reader()
  113. 	        {
  114. 	            din = new DataInputStream(System.in);
  115. 	            buffer = new byte[BUFFER_SIZE];
  116. 	            bufferPointer = bytesRead = 0;
  117. 	        }
  118.  
  119. 	        public Reader(String file_name) throws IOException
  120. 	        {
  121. 	            din = new DataInputStream(new FileInputStream(file_name));
  122. 	            buffer = new byte[BUFFER_SIZE];
  123. 	            bufferPointer = bytesRead = 0;
  124. 	        }
  125.  
  126. 	        public String readLine() throws IOException
  127. 	        {
  128. 	            byte[] buf = new byte[64]; // line length
  129. 	            int cnt = 0, c;
  130. 	            while ((c = read()) != -1)
  131. 	            {
  132. 	                if (c == '\n')
  133. 	                    break;
  134. 	                buf[cnt++] = (byte) c;
  135. 	            }
  136. 	            return new String(buf, 0, cnt);
  137. 	        }
  138.  
  139. 	        public int nextInt() throws IOException
  140. 	        {
  141. 	            int ret = 0;
  142. 	            byte c = read();
  143. 	            while (c <= ' ')
  144. 	                c = read();
  145. 	            boolean neg = (c == '-');
  146. 	            if (neg)
  147. 	                c = read();
  148. 	            do
  149. 	            {
  150. 	                ret = ret * 10 + c - '0';
  151. 	            }  while ((c = read()) >= '0' && c <= '9');
  152.  
  153. 	            if (neg)
  154. 	                return -ret;
  155. 	            return ret;
  156. 	        }
  157.  
  158. 	        public long nextLong() throws IOException
  159. 	        {
  160. 	            long ret = 0;
  161. 	            byte c = read();
  162. 	            while (c <= ' ')
  163. 	                c = read();
  164. 	            boolean neg = (c == '-');
  165. 	            if (neg)
  166. 	                c = read();
  167. 	            do {
  168. 	                ret = ret * 10 + c - '0';
  169. 	            }
  170. 	            while ((c = read()) >= '0' && c <= '9');
  171. 	            if (neg)
  172. 	                return -ret;
  173. 	            return ret;
  174. 	        }
  175.  
  176. 	        public double nextDouble() throws IOException
  177. 	        {
  178. 	            double ret = 0, div = 1;
  179. 	            byte c = read();
  180. 	            while (c <= ' ')
  181. 	                c = read();
  182. 	            boolean neg = (c == '-');
  183. 	            if (neg)
  184. 	                c = read();
  185.  
  186. 	            do {
  187. 	                ret = ret * 10 + c - '0';
  188. 	            }
  189. 	            while ((c = read()) >= '0' && c <= '9');
  190.  
  191. 	            if (c == '.')
  192. 	            {
  193. 	                while ((c = read()) >= '0' && c <= '9')
  194. 	                {
  195. 	                    ret += (c - '0') / (div *= 10);
  196. 	                }
  197. 	            }
  198.  
  199. 	            if (neg)
  200. 	                return -ret;
  201. 	            return ret;
  202. 	        }
  203.  
  204. 	        private void fillBuffer() throws IOException
  205. 	        {
  206. 	            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  207. 	            if (bytesRead == -1)
  208. 	                buffer[0] = -1;
  209. 	        }
  210.  
  211. 	        private byte read() throws IOException
  212. 	        {
  213. 	            if (bufferPointer == bytesRead)
  214. 	                fillBuffer();
  215. 	            return buffer[bufferPointer++];
  216. 	        }
  217.  
  218. 	        public void close() throws IOException
  219. 	        {
  220. 	            if (din == null)
  221. 	                return;
  222. 	            din.close();
  223. 	        }
  224. 	    }	
  225.  
  226.  
  227. }
Runtime error #stdin #stdout #stderr 0.05s 711168KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.lang.NumberFormatException: null
	at java.lang.Integer.parseInt(Integer.java:542)
	at java.lang.Integer.parseInt(Integer.java:615)
	at Main.main(Main.java:21)
https://ideone.com/xvbBpd
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!