日期：2025年4月10日
ZeroJudge 題目連結：i377. 單字找找看 (Word)
解題想法
這題寫起來很長，因為要找 8 個方向，依照題目對於答案的要求，搜尋的方向依序是左上、正上、右上、正左、正右、左下、正下、右下。
Python 程式碼
使用時間約為 22 ms，記憶體約為 3.5 MB，通過測試。
import sys
def solve(g, t): # 輸入字串方格 g，找目標字串 t
m, n = len(g) -1, len(g[0]) -1 # 列數減 1，每列長度減 1
tl = len(t) # t 的長度
for r in range(m): # 依序掃過每列
for c in range(n): # 依序掃過每欄
found = True # 是否找到答案，先找左上方
for i in range(tl):
if t[i] != grid[r-i][c-i]: # 只要字元不相等就可以中止迴圈
found = False; break
if found: # 如果找到答案，印出起點、終點，記得加 1
print(f"{r+1:d} {c+1:d}\n{r-tl+2:d} {c-tl+2:d}")
return # 中止函式
found = True # 是否找到答案，找正上方
for i in range(tl):
if t[i] != grid[r-i][c]:
found = False; break
if found:
print(f"{r+1:d} {c+1:d}\n{r-tl+2:d} {c+1:d}")
return
found = True # 是否找到答案，找右上方
for i in range(tl):
if t[i] != grid[r-i][c+i]:
found = False; break
if found:
print(f"{r+1:d} {c+1:d}\n{r-tl+2:d} {c+tl:d}")
return
found = True # 是否找到答案，找正左方
for i in range(tl):
if t[i] != grid[r][c-i]:
found = False; break
if found:
print(f"{r+1:d} {c+1:d}\n{r+1:d} {c-tl+2:d}")
return
found = True # 是否找到答案，找正右方
for i in range(tl):
if t[i] != grid[r][c+i]:
found = False; break
if found:
print(f"{r+1:d} {c+1:d}\n{r+1:d} {c+tl:d}")
return
found = True # 是否找到答案，找左下方
for i in range(tl):
if t[i] != grid[r+i][c-i]:
found = False; break
if found:
print(f"{r+1:d} {c+1:d}\n{r+tl:d} {c-tl+2:d}")
return
found = True # 是否找到答案，找正下方
for i in range(tl):
if t[i] != grid[r+i][c]:
found = False; break
if found:
print(f"{r+1:d} {c+1:d}\n{r+tl:d} {c+1:d}")
return
found = True # 是否找到答案，找右下方
for i in range(tl):
if t[i] != grid[r+i][c+i]:
found = False; break
if found:
print(f"{r+1:d} {c+1:d}\n{r+tl:d} {c+tl:d}")
return
print("NO"); return
for line in sys.stdin:
m, n = map(int, line.split()) # 表格 m*n
grid = [input().strip().lower()+"0" for _ in range(m)] # 加 0 作為哨兵
grid.append("0"*(n+1))
solve(grid, input().strip().lower())
C++ 程式碼
使用時間約為 3 ms，記憶體約為 356 kB，通過測試。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
void solve(vector<string>&, string);
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int m, n; // 表格 m*n
while(cin >> m >> n) {
m += 2; n += 2; // 先加 2
vector<string> grid (m); // 儲存資料的方格
for(int i=0; i<n; i++) grid[0] += '0'; // 最上面加一列 0
for(int i=0; i<n; i++) grid[m-1] += '0'; // 最下面加一列 0
for(int i=1; i<m-1; i++) {
string s; cin >> s; // 暫存用的字串
transform(s.begin(), s.end(), s.begin(), ::tolower); // 轉成小寫字母
grid[i] = "0" + s + "0"; // 兩端加 0 存入 grid[i]
}
string t; cin >> t; // 目標字串
transform(t.begin(), t.end(), t.begin(), ::tolower); // 轉成小寫字母
solve(grid, t); // 呼叫 solve 求解
}
return 0;
}
void solve(vector<string>& grid, string t) { // 輸入字串方格 grid，找目標字串 t
int m = (int)grid.size(), n = (int)grid[0].size(); // 列數，每列長度
int tl = (int)t.size(); // t 的長度
for(int r=1; r<m-1; r++) { // 依序掃過每列
for(int c=1; c<n-1; c++) { // 依序掃過每欄
bool found = true; // 是否找到答案，先找左上方
for(int i=0; i<tl; i++) {
if (t[i] != grid[r-i][c-i]) { // 只要字元不相等就可以中止迴圈
found = false; break;
}
}
if (found) { // 如果找到答案，印出起點、終點
cout << r << " " << c << "\n" << r-tl+1 << " " << c-tl+1 << "\n";
return; // 中止函式
}
found = true; // 找正上方
for(int i=0; i<tl; i++) {
if (t[i] != grid[r-i][c]) { // 只要字元不相等就可以中止迴圈
found = false; break;
}
}
if (found) { // 如果找到答案，印出起點、終點
cout << r << " " << c << "\n" << r-tl+1 << " " << c << "\n";
return; // 中止函式
}
found = true; // 找右上方
for(int i=0; i<tl; i++) {
if (t[i] != grid[r-i][c+i]) { // 只要字元不相等就可以中止迴圈
found = false; break;
}
}
if (found) { // 如果找到答案，印出起點、終點
cout << r << " " << c << "\n" << r-tl+1 << " " << c+tl-1 << "\n";
return; // 中止函式
}
found = true; // 找正左方
for(int i=0; i<tl; i++) {
if (t[i] != grid[r][c-i]) { // 只要字元不相等就可以中止迴圈
found = false; break;
}
}
if (found) { // 如果找到答案，印出起點、終點
cout << r << " " << c << "\n" << r << " " << c-tl+1 << "\n";
return; // 中止函式
}
found = true; // 找正右方
for(int i=0; i<tl; i++) {
if (t[i] != grid[r][c+i]) { // 只要字元不相等就可以中止迴圈
found = false; break;
}
}
if (found) { // 如果找到答案，印出起點、終點
cout << r << " " << c << "\n" << r << " " << c+tl-1 << "\n";
return; // 中止函式
}
found = true; // 找左下方
for(int i=0; i<tl; i++) {
if (t[i] != grid[r+i][c-i]) { // 只要字元不相等就可以中止迴圈
found = false; break;
}
}
if (found) { // 如果找到答案，印出起點、終點
cout << r << " " << c << "\n" << r+tl-1 << " " << c-tl+1 << "\n";
return; // 中止函式
}
found = true; // 找正下方
for(int i=0; i<tl; i++) {
if (t[i] != grid[r+i][c]) { // 只要字元不相等就可以中止迴圈
found = false; break;
}
}
if (found) { // 如果找到答案，印出起點、終點
cout << r << " " << c << "\n" << r+tl-1 << " " << c << "\n";
return; // 中止函式
}
found = true; // 找右下方
for(int i=0; i<tl; i++) {
if (t[i] != grid[r+i][c+i]) { // 只要字元不相等就可以中止迴圈
found = false; break;
}
}
if (found) { // 如果找到答案，印出起點、終點
cout << r << " " << c << "\n" << r+tl-1 << " " << c+tl-1 << "\n";
return; // 中止函式
}
}
}
cout << "NO\n";
return;
}
沒有留言:
張貼留言