# 1122 程式設計實習III (資訊一乙) Week06 作業 BFS 參考資料：https://ithelp.ithome.com.tw/articles/10334101 ## 1. Shortest Path Finder --- ### 題目敘述 You are tasked with finding the shortest path from a given starting point to an ending point on a two-dimensional plane. The plane consists of both passable roads and impassable walls. Your goal is to determine the minimum distance required to traverse from the starting point to the ending point, considering only the passable roads. If it's impossible to reach the ending point, output "0" indicating the absence of a viable path. --- ### 題目輸入 The input file consists of multiple test cases. Each test case starts with a line containing a positive integer $N$ ($1 \le N \le 100$), denoting the number of test cases. For each test case, the following lines contain data representing the two-dimensional plane. The first line of each test case contains six integers separated by spaces: $n$ and $m$ ($1 \le n,m \le 100$) representing the number of rows and columns of the plane, followed by the coordinates of the starting point (row and column), and the coordinates of the ending point (row and column). Starting from the second line, there will be an n * m two-dimensional array where each element can be either "0" (indicating a passable road) or "1" (indicating a wall). --- ### 題目輸出 For each test case, output a single line representing the minimum distance required to reach the ending point from the starting point. If it's impossible to reach the ending point, output "0". --- ### 範例輸入 ``` 2 5 6 3 1 3 4 000000 011101 000010 011000 000010 10 10 1 1 10 10 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 ``` --- ### 範例輸出 ``` 4 19 ``` --- ## 2. Update the string --- ### 題目敘述 You have an initial string of length $n$, where each character is a lowercase English letter. Following this, there are $q$ modifications. Each modification involves rearranging the old string into a new string. Specifically, each modification provides a permutation $P$, where each position $i$ represents that the $i$th character of the old string should be copied to position $P[i]$ in the new string. For example: - If the old string is "abac" and $P = [4, 1, 3, 2]$, the new string would be "bcaa". - If the old string is "bcaa" and $P = [1, 2, 3, 4]$, the new string remains "bcaa". - If the old string is "bcaa" and $P = [2, 3, 4, 1]$, the new string would be "abca". In each modification, the new string produced becomes the old string for the subsequent modification. The initial string used for the first modification is the original string provided. --- ### 題目輸入 The first line has two integers $K$ and $Q$. ($1 \le K,Q \le 20$) The second line contains the initial string $s$ with a length of $K$. Following this, there are $Q$ lines, each line containing a permutation $P_i$. --- ### 題目輸出 Output the string after each update. --- ### 範例輸入 ``` 5 4 abcde 2 1 3 5 4 5 1 2 4 3 4 1 2 3 5 3 1 4 5 2 ``` ``` 4 3 abac 4 1 3 2 1 2 3 4 2 3 4 1 ``` --- ### 範例輸出 ``` baced acdeb cdeab dbcea ``` ``` bcaa bcaa abca ``` --- ## 作業繳交方式 - 交至ilearn作業繳交區 - 原始碼檔名以 學號_題號.c 或 學號_題號.cpp 命名 (example. D1109070_01.c 或是 D1109070_01.cpp) - 兩題分兩個檔案上傳 - 在OJ上面有可以讓你檢視是否正確的作答區 - 名稱: [112 (資訊一乙) 程式設計III Week06 作業] - 密碼: CPECrash