Submission #3629074

---

Source Code Expand

#include <iostream>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
const int INF = 1 << 28;

int rec[101][101][101][4];
char board[101][101];

struct Elem {
    int x, y, str_pos, dir, cost;
    Elem() {}
    Elem(int a, int b, int c, int d, int e) : x(a), y(b), str_pos(c), dir(d), cost(e) {}
};

int main() {
    int N, M, L; cin >> N >> M >> L;
    string s; cin >> s;
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            cin >> board[i][j];
        }
    }

    queue<Elem> que;
    fill(rec[0][0][0], rec[N][0][0], INF);
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            rec[i][j][0][0] = 0;
            que.push(Elem(i, j, 0, 0, 0));
        }
    }

    while(que.size()) {
        Elem cur = que.front(); que.pop();
        if(cur.str_pos == s.length()) continue;

        int val = cur.cost;
        if(val > rec[cur.x][cur.y][cur.str_pos][cur.dir]) continue;
        for(int k=0; k<4; k++) {
            if(cur.str_pos != 0 and k == cur.dir) continue;
            int cx = cur.x + dx[k], cy = cur.y + dy[k], add = 1;
            for(; cx>=0 and cx<N and cy>=0 and cy<M; cx+=dx[k], cy+=dy[k], add++) {
                if(board[cx][cy] == s[cur.str_pos]) break;
            }

            if(cx < 0 or cx >= N or cy < 0 or cy >= M) continue;
            if(rec[cx][cy][cur.str_pos+1][k] > val + add) {
                rec[cx][cy][cur.str_pos+1][k] = val + add;
                que.push(Elem(cx, cy, cur.str_pos+1, k, val + add));
            }
        }
    }

    int ans = INF;
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            for(int k=0; k<4; k++) {
                ans = min(ans, rec[i][j][s.length()][k]);
            }
        }
    }

    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}

Submission Info

Judge Result