输入n和地图 输出步数

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
char s;
int n;
string start;

char flap(char s) {
    if (s == '#') return '.';
    if (s == '.') return '#';
}
int dfs() {
    queue<string> q;
    unordered_map<string, int> d;
    d[start] = 0;
    q.push(start);

    string end;
    for (int i = 0;i < n * n;i++) {
        end += "#";
    }

    while (q.size()) {
        auto t = q.front();
        q.pop();
        if (t == end) return d[t];
        int distance = d[t];

        for (int i = 0;i <n;i++) {
            for (int a = 0;a <= i ;a++) {
                int b = i - a;
                t[a * n + b] = flap(t[a * n + b]);
            }
            if (!d.count(t)) {
                d[t] = distance + 1;
                q.push(t);
            }
            for (int a = 0;a <= i;a++) {
                int b = i - a;
                t[a * n + b] = flap(t[a * n + b]);
            }
        }
        for (int i = n-1;i > 0;i--) {
            for (int a = n-1;a >= i;a--) {
                int b = n - 1 - a + i;
                t[a * n + b] = flap(t[a * n + b]);
            }
            if (!d.count(t)) {
                d[t] = distance + 1;
                q.push(t);
            }
            for (int a = n-1;a >= i;a--) {
                int b = n - 1 - a + i;
                t[a * n + b] = flap(t[a * n + b]);
            }
        }

        for (int g = 0;g < n;g++) {
            for (int a = 0;a <= g;a++) {
                int b = a + n - g - 1;
                t[a * n + b] = flap(t[a * n + b]);
            }
            if (!d.count(t)) {
                d[t] = distance + 1;
                q.push(t);
            }
            for (int a = 0;a <= g;a++) {
                int b = a + n - g - 1;
                t[a * n + b] = flap(t[a * n + b]);
            }
        }
        for (int g = n - 1;g > 0;g--) {
            for (int a = n - 1;a >= g;a--) {
                int b = a - g;
                t[a * n + b] = flap(t[a * n + b]);
            }
            if (!d.count(t)) {
                d[t] = distance + 1;
                q.push(t);
            }
            for (int a = n - 1;a >= g;a--) {
                int b = a - g;
                t[a * n + b] = flap(t[a * n + b]);
            }
        }

    }

    return -1;
}
int main() {
    cin >> n;
    for (int i = 0;i < n * n;i++) {
        cin >> s;
        start += s;
    }
    cout << dfs() << endl;
}

对于一个爆搜新手来说，调对了之后简直要哭了。果然还是太菜了。
好的我们现在把它改成谷歌格式。

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
int n;


char flap(char s) {
    if (s == '#') return '.';
    if (s == '.') return '#';
}
int dfs(string start) {
    queue<string> q;
    unordered_map<string, int> d;
    d[start] = 0;
    q.push(start);

    string end;
    for (int i = 0;i < n * n;i++) {
        end += "#";
    }

    while (q.size()) {
        auto t = q.front();
        q.pop();
        if (t == end) return d[t];
        int distance = d[t];

        for (int i = 0;i <n;i++) {
            for (int a = 0;a <= i ;a++) {
                int b = i - a;
                t[a * n + b] = flap(t[a * n + b]);
            }
            if (!d.count(t)) {
                d[t] = distance + 1;
                q.push(t);
            }
            for (int a = 0;a <= i;a++) {
                int b = i - a;
                t[a * n + b] = flap(t[a * n + b]);
            }
        }
        for (int i = n-1;i > 0;i--) {
            for (int a = n-1;a >= i;a--) {
                int b = n - 1 - a + i;
                t[a * n + b] = flap(t[a * n + b]);
            }
            if (!d.count(t)) {
                d[t] = distance + 1;
                q.push(t);
            }
            for (int a = n-1;a >= i;a--) {
                int b = n - 1 - a + i;
                t[a * n + b] = flap(t[a * n + b]);
            }
        }

        for (int g = 0;g < n;g++) {
            for (int a = 0;a <= g;a++) {
                int b = a + n - g - 1;
                t[a * n + b] = flap(t[a * n + b]);
            }
            if (!d.count(t)) {
                d[t] = distance + 1;
                q.push(t);
            }
            for (int a = 0;a <= g;a++) {
                int b = a + n - g - 1;
                t[a * n + b] = flap(t[a * n + b]);
            }
        }
        for (int g = n - 1;g > 0;g--) {
            for (int a = n - 1;a >= g;a--) {
                int b = a - g;
                t[a * n + b] = flap(t[a * n + b]);
            }
            if (!d.count(t)) {
                d[t] = distance + 1;
                q.push(t);
            }
            for (int a = n - 1;a >= g;a--) {
                int b = a - g;
                t[a * n + b] = flap(t[a * n + b]);
            }
        }

    }

    return -1;
}
int main() {
    int T,casei=0;
    cin >> T;
    while (T--) {
        casei++;
        cin >> n;
        string start;
        for (int i = 0;i < n * n;i++) {
            char s;
            cin >> s;
            start += s;
        }
        cout <<"Case #"<<casei<<": "<< dfs(start) << endl;
    }
    return 0;
}

跑出来测试数据都是对的……但是谷歌提交上去说MLE了，能超过1GB的memory我也是厉害……