G - Patrol Robot UVA - 1600

#include <iostream>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <cmath>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <cstdio>
using namespace std;
#define INF 0x3f3f3f3f
int m, n, k;
int a[25][25];
bool flag[25][25][25];
int cx[] = {0,0,-1,1};
int cy[] = {-1,1,0,0};
struct road {
	int x, y;
	int k, c;
}t;
int bfs() {
	queue<road> q;
	memset(flag, false, sizeof(flag));
	t.x = t.y = 0;
	t.c = t.k = 0;
	q.push(t);
	while (!q.empty()) {
		t = q.front();
		q.pop();
		for (int i = 0; i < 4; ++i) {
			road t0;
			t0.x = t.x + cx[i];
			t0.y = t.y + cy[i];
			t0.k = t.k;
			t0.c = t.c;
			if (t0.x < 0 || t0.y < 0 || t0.x >= n || t0.y >= m) {
				continue;
			}
			if (a[t0.x][t0.y]) {
				t0.k++;
				if (t0.k > k) {
					continue;
				}
			}
			else {
				t0.k = 0;
			}
			if (flag[t0.x][t0.y][t0.k]) {
				continue;
			}
			flag[t0.x][t0.y][t0.k] = true;
			++t0.c;
			if (t0.x == n - 1 && t0.y == m - 1) {
				return t0.c;
			}
			q.push(t0);
		}
	}
	return -1;
}
int main() {
	int T;
	cin >> T;
	while (T--) {
		scanf("%d%d%d", &n, &m,&k);
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				scanf("%d", &a[i][j]);
			}
		}
		cout << bfs() << endl;
	}
	return 0;
}

不难想到多一维表示到当前位置时已连续走过的障碍。