#ifndef Nhoksocqt1
#include "robot.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 20;
const int lx[] = {0, +1, 0, -1}, ly[] = {-1, 0, +1, 0};
const int tt[] = {2, 1, 0, 3};
const char dir[] = {'W', 'S', 'E', 'N'};
#ifdef Nhoksocqt1
map<vector<int>, ii> Map;
int col[MAXN][MAXN], id[256];
bool A[MAXN][MAXN];
void set_instruction(vector<int> S, int Z, char A) {
Map[S] = ii(Z, A);
}
void simulate(int H, int W, bool a[][MAXN]) {
for (int i = 0; i < 4; ++i)
id[dir[i]] = i;
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j)
col[i][j] = (A[i][j] < 0) ? A[i][j] : 0;
}
int x(0), y(0);
while(1) {
vector<int> state;
state.push_back(col[x][y]);
for (int id = 0; id < 4; ++id) {
int u(x + lx[id]), v(y + ly[id]);
if(min(u, v) < 0 || u >= H || v >= W) {
state.push_back(-2);
continue;
}
if(A[u][v]) {
state.push_back(-1);
continue;
}
state.push_back(col[u][v]);
}
cout << "STATE: ";
for (int it = 0; it < sz(state); ++it)
cout << state[it] << ' '; cout << '\n';
if(Map.find(state) == Map.end()) {
cout << "CAN NOT FIND STATE: ";
for (int it = 0; it < sz(state); ++it)
cout << state[it] << ' '; cout << '\n';
return;
}
ii z = Map[state];
col[x][y] = z.fi;
cout << x << ' ' << y << ' ' << z.fi << ' ' << char(z.se) << '\n';
if(z.se == 'T') {
cout << "FIND PATH TO (" << H - 1 << ", " << W - 1 << ") OK!!\n";
cout << "GRID COLOR NOW:\n";
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j)
cout << col[i][j] << " \n"[j + 1 == W];
}
return;
}
int idt = id[z.se];
x += lx[idt], y += ly[idt];
cout << "GRID COLOR NOW:\n";
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j)
cout << col[i][j] << " \n"[j + 1 == W];
}
}
}
#endif // Nhoksocqt1
void setp(vector<int> state) {
int cnt(0);
for (int it = 0; it < sz(state); ++it)
cnt += (state[it] == -2);
if(cnt > 2)
return;
if(state[2] == -2 && state[3] == -2) {
set_instruction(state, 1, 'T');
return;
}
bool has0(0);
for (int it = 1; it < sz(state); ++it)
has0 |= (state[it] == 0);
if(has0) {
for (int it = 0; it < 4; ++it) {
if(state[tt[it] + 1] == 0)
set_instruction(state, 1, dir[tt[it]]);
}
return;
}
for (int it = 0; it < 4; ++it) {
if(state[tt[it] + 1] == 1)
set_instruction(state, 2, dir[tt[it]]);
}
return;
}
void program_pulibot(void) {
for (int here = 0; here <= 2; ++here) {
for (int west = -2; west <= 2; ++west) {
for (int south = -2; south <= 2; ++south) {
for (int east = -2; east <= 2; ++east) {
for (int north = -2; north <= 2; ++north) {
setp({here, west, south, east, north});
}
}
}
}
}
}
#ifdef Nhoksocqt1
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "robot"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
int _H, _W;
cin >> _H >> _W;
for (int i = 0; i < _H; ++i) {
for (int j = 0; j < _W; ++j) {
char c;
cin >> c;
A[i][j] = (c == '1');
}
}
program_pulibot();
simulate(_H, _W, A);
return 0;
}
#endif // Nhoksocqt1
