RobotKing

Problem Statement

Definition

Class:

RobotKing

Method:

calculateWinProbability

Parameters:

int, String[], String[]

Returns:

double

Method signature:

double calculateWinProbability(int maxTurns, String[] robotMoves, String[] board)

(be sure your method is public)

Notes

• è™½ç„¶çŽ©å®¶åœ¨æœ€å¼€å§‹ä¸çŸ¥é“æ¯ä¸ªæœºå™¨äººçš„é¢„è®¢æ–¹å‘ï¼Œä½†æ˜¯åœ¨æœºå™¨äººè¡ŒåŠ¨åŽï¼ˆå¦‚æžœæœ‰å®žé™ ç§»åŠ¨ï¼‰çŽ©å®¶å°±èƒ½å¤ŸçŸ¥é“è¿™ä¸ªæœºå™¨äººå¯¹åº”çš„æ–¹å‘å¹¶æŠŠè¿™ä¸ªä¿¡æ¯ç”¨äºŽä¹‹åŽçš„å†³ç­–ä¸­ã€‚
• è¿”å›žå€¼å¿ é¡»ä¿è¯ç»å¯¹å’Œç›¸å¯¹è¯¯å·®ä¸è¶ è¿‡1e-9。

Constraints

• maxTurns 取值于1到100（含1和100）。
• robotMoves åŒ å«1到5ä¸ªå ƒç´ ï¼ˆå«1和5）。
• robotMovesä¸­çš„æ¯ä¸ªå ƒç´ éƒ½æ˜¯å¦‚é¢˜ç›®æè¿°ä¸­æ‰€è¯´çš„"Direction1 Direction2 P"æ ¼å¼ï¼Œå¹¶ä¸”æœ€å¼€å§‹å’Œæœ€åŽéƒ½æ²¡æœ‰å¤šä½™ç©ºæ ¼ï¼Œç›¸é‚»å ƒç´ ä¹‹é—´ä»¥ä¸€ä¸ªç©ºæ ¼åˆ†éš”ã€‚
• robotMoves çš„åŒä¸€ä¸ªå ƒç´ ä¸­çš„Direction1和Direction2是肯定不同的。
• robotMoves中的每个P都在0到100之间（含0和100）。
• robotMoves中的所有P都没有无意义的0前缀。
• boardåŒ å«2到15ä¸ªå ƒç´ ï¼ˆå«2和15）。
• boardçš„æ¯ä¸ªå ƒç´ åŒ å«2到15个字符（含2和15）。
• boardçš„æ¯ä¸ªå ƒç´ éƒ½åŒ å«ç›¸åŒä¸ªæ•°çš„å­—ç¬¦ã€‚
• boardçš„æ¯ä¸ªå ƒç´ éƒ½åªåŒ å«'K'、'.'、'S'和'#'。
• boardåŒ å«æœ‰æ°å¥½ä¸€ä¸ª'K'。
• boardåŒ å«è‡³å°‘ä¸€ä¸ª'S'。

Examples

1. 10

   {"R L 25"}

   {"S.",
    "..",
    "..",
    "K."}

   Returns: 0.75

2. 33

   {"U D 50", "R L 100", "R L 100"}

   {"...",
    "K.S",
    "..."}

   Returns: 1.0

   这个例子中的最好策略是在第一轮不移动国王。

3. 5

   {"R L 50", "R L 50"}

   {"S..###",
    "##..##",
    "###.K#"}

   Returns: 0.25

   只有一种可能把国王在5è½®æˆ–è€ ä»¥å† ç§»åŠ¨åˆ°èƒœåˆ©æ ¼å­ï¼Œä¹Ÿå°±æ˜¯ä¸¤ä¸ªæœºå™¨äººé¢„è®¢ç§»åŠ¨æ–¹å‘éƒ½æ˜¯å‘å·¦çš„æƒ å†µã€‚

4. 50

   {"D U 100", "U R 47"}

   {".......S",
    "S...####",
    "...#K###"}

   Returns: 1.0

   第一个机器人的移动方向是100%å‘ä¸‹çš„ï¼Œè€Œç¬¬äºŒä¸ªæœºå™¨äººçš„ç§»åŠ¨æ–¹å‘æ˜¯å‘ä¸Šæˆ–è€ å‘å³ã€‚åœ¨çŽ©å®¶ç¬¬ä¸€æ¬¡ç§»åŠ¨æ—¶ï¼Œä»–åº”è¯¥æŠŠå›½çŽ‹æ²¿å¯¹è§’çº¿å‘å·¦ä¸Šæ ¼å­ç§»åŠ¨ã€‚ä¹‹åŽç¬¬ä¸€ä¸ªæœºå™¨äººå› ä¸ºä¸‹é¢æ ¼å­æœ‰éšœç¢ç‰©è€Œä¸ä¼šç§»åŠ¨å›½çŽ‹ã€‚è€Œç¬¬äºŒä¸ªæœºå™¨äººå¯èƒ½å‘ä¸Šç§»åŠ¨æˆ–è€ å› ä¸ºå³ä¾§æœ‰éšœç¢ç‰©è€Œä¸ç§»åŠ¨ã€‚ä¸¤ç§æƒ å†µä¸‹ï¼ŒçŽ©å®¶éƒ½ä¼šçŸ¥é“è¿™ä¸ªæœºå™¨äººçš„é¢„è®¢ç§»åŠ¨æ–¹å‘ã€‚å¦‚æžœæ˜¯å‘ä¸Šï¼Œåˆ™çŽ©å®¶å¯ä»¥é€šè¿‡åˆ°è¾¾å·¦ä¾§çš„èƒœåˆ©æ ¼å­èŽ·èƒœï¼›å¦‚æžœæ˜¯å‘å³ï¼Œåˆ™çŽ©å®¶å¯ä»¥é€šè¿‡åˆ°è¾¾å³ä¾§çš„èƒœåˆ©æ ¼å­è€ŒèŽ·èƒœã€‚

5. 5

   {"L D 50"}

   {"####K",
    "###.#",
    "#..##",
    "S..S#"}

   Returns: 1.0

   ç¬¬ä¸€è½®çŽ©å®¶å‘å·¦ä¸‹ç§»åŠ¨å›½çŽ‹ï¼Œç¬¬äºŒè½®æœºå™¨äººæ˜¯æ— æ³•ç§»åŠ¨çš„ï¼Œæ‰€ä»¥çŽ©å®¶ä»ç„¶ä¸çŸ¥é“æœºå™¨äººçš„é¢„è®¢æ–¹å‘ã€‚ç¬¬ä¸‰è½®çŽ©å®¶å†å‘å·¦ä¸‹è§’ç§»åŠ¨åŽï¼Œæœºå™¨äººå¯ä»¥å‘å·¦æˆ–è€ ä¸‹ç§»åŠ¨ã€‚çŽ©å®¶çŸ¥é“äº†æœºå™¨äººçš„é¢„è®¢æ–¹å‘åŽï¼Œå†³å®šå‘å“ªä¸ªèƒœåˆ©æ ¼å­ç§»åŠ¨ï¼Œå‡å¯ä»¥åœ¨5è½®å† èŽ·èƒœã€‚