hihoCoder 1094：Lost in the City——3×3 區域匹配含旋轉

題目描述

給定 N×M 城市地圖（字符表示建築類型）和小 Hi 周圍 3×3 區域（Hi 在中心），Hi 可能面朝任意方向（即 3×3 可旋轉 0°/90°/180°/270°）。找出所有可能位置，按行優先列次序輸出。

解題思路：枚舉 + 旋轉匹配

1. 讀入地圖和 3×3 觀測區域
2. 預計算觀測區域的 4 種旋轉態
3. 掃描地圖每個非邊界點 (i,j)：
   • 若中心字符匹配
   • 檢查 4 個旋轉態是否與地圖 [i-1..i+1][j-1..j+1] 完全一致
   • 匹配則記錄位置（輸出 1-based 座標）

旋轉實現

void rotate90(char a[3][3]) { // 就地順時針旋轉 90°
    char tmp[3][3];
    for(int i=0;i<3;++i) for(int j=0;j<3;++j) tmp[i][j]=a[i][j];
    for(int i=0;i<3;++i) for(int j=0;j<3;++j) a[j][2-i]=tmp[i][j];
}

C++ 實現（核心）

bool match(char map[205][205], int x, int y, char pat[3][3]) {
    for(int i=0;i<3;++i)
        for(int j=0;j<3;++j)
            if(map[x+i-1][y+j-1] != pat[i][j]) return false;
    return true;
}

int main() {
    int n,m; while(scanf("%d%d",&n,&m)==2) {
        char map[205][205], obs[3][3], r1[3][3], r2[3][3], r3[3][3];
        for(int i=0;i

複雜度

時間：O(N×M) × 4 × 9 ≈ 1.3×10⁶，極快
空間：O(N×M)