[テストコードC+]文字

今日の質問

アルファベット

方法

私の答え

#include<iostream>
#include <algorithm>
using namespace std;
int r, c;
const int MAX = 20;
char arr[MAX][MAX];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int alpha[26] = {false};

int dfs(int y, int x){
    int maxi = 0;
    for(int i=0;i<4;i++){
        int mx = x + dx[i];
        int my = y + dy[i];
        int al = arr[my][mx]-'A';
        if(mx >= c || mx <0 || my >= r || my<0)
            continue;
        if(alpha[al] == false){
            alpha[al] = true;
            maxi = max(maxi, dfs(my, mx));
            alpha[al] = false;
        }
    }
    return maxi+1;
}

int solution(){
    alpha[arr[0][0] - 'A'] = true;
    return dfs(0, 0);
}

別の解釈

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

using std::scanf;
using std::printf;
using std::vector;
using std::unique;
using std::pair;
using std::swap;

using pii = pair<int, int>;

char board[25][25];
vector<pair<int, int> > s;

int main() {
    int h, w; scanf("%d%d", &h, &w);
    for (int ih = 0; ih < h; ++ih) {
        scanf("%22s", board[ih]);
    }
    s.push_back({0, 1 << board[0][0] - 'A'});
    int gen = 0;
    for ( ; !s.empty(); ++gen) {
        vector<pair<int, int> > olds;
        swap(s, olds);
        olds.erase(unique(olds.begin(), olds.end()), olds.end());

        for (auto& pr : olds) {
            const int p = pr.first;
            const int v = pr.second;
            const int ds[4] = {1, -1, w, -w};
            for (int d : ds) {
                int np = p + d;
                if (np < 0 || np >= h * w || (d % w != 0 && p / w != np / w)) { continue; }
                int nv = v | 1 << board[np / w][np % w] - 'A';
                if (nv == v) continue;
                s.push_back({np, nv});
            }
        }
    }
    printf("%d\n", gen);
}

学ぶべきところ