Untitled
unknown
plain_text
4 years ago
11 kB
5
Indexable
// be name khoda
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int a[maxn][maxn];
int dis[maxn][maxn][4];
bool seen[maxn][maxn];
vector <int> g1x;
vector <int> g1y;
vector <int> g2x;
vector <int> g2y;
vector <int> g3x;
vector <int> g3y;
bool moj12;
bool moj13;
bool moj23;
queue <int> qx;
queue <int> qy;
int dis1[maxn][maxn];
int dis11[maxn][maxn];
int dis2[maxn][maxn];
int dis3[maxn][maxn];
int r1to2 = -1;
int r1to3 = -1;
int r2to3 = -1;
bool mas1to2;
bool mas1to3;
bool mas2to3;
void mamad(int x, int y, int hight){
hight++;
if (!seen[x][y+1]){
if (a[x][y+1] == 4){
dis3[x][y+1] = hight;
seen[x][y+1]= true;
qx.push(x);
qy.push(y+1);
}
}
if (!seen[x+1][y]){
if (a[x+1][y] == 4){
dis3[x+1][y] = hight;
seen[x+1][y]= true;
qx.push(x+1);
qy.push(y);
}
}
if (!seen[x][y-1]){
if (a[x][y-1] == 4){
dis3[x][y-1] = hight;
seen[x][y-1]= true;
qx.push(x);
qy.push(y-1);
}
}
if (!seen[x-1][y]){
if (a[x-1][y] == 4){
dis3[x-1][y] = hight;
seen[x-1][y]= true;
qx.push(x-1);
qy.push(y);
}
}
}
void hasan(int x, int y, int hight){
hight++;
if (!seen[x][y+1]){
if (a[x][y+1] == 4){
dis2[x][y+1] = hight;
seen[x][y+1]= true;
qx.push(x);
qy.push(y+1);
}
}
if (!seen[x+1][y]){
if (a[x+1][y] == 4){
dis2[x+1][y] = hight;
seen[x+1][y]= true;
qx.push(x+1);
qy.push(y);
}
}
if (!seen[x][y-1]){
if (a[x][y-1] == 4){
dis2[x][y-1] = hight;
seen[x][y-1]= true;
qx.push(x);
qy.push(y-1);
}
}
if (!seen[x-1][y]){
if (a[x-1][y] == 4){
dis2[x-1][y] = hight;
seen[x-1][y]= true;
qx.push(x-1);
qy.push(y);
}
}
}
void jafar(int x, int y, int hight){
hight++;
if (!seen[x][y+1]){
if (a[x][y+1] == 4){
dis11[x][y+1] = hight;
seen[x][y+1]= true;
qx.push(x);
qy.push(y+1);
}
}
if (!seen[x+1][y]){
if (a[x+1][y] == 4){
dis11[x+1][y] = hight;
seen[x+1][y]= true;
qx.push(x+1);
qy.push(y);
}
}
if (!seen[x][y-1]){
if (a[x][y-1] == 4){
dis11[x][y-1] = hight;
seen[x][y-1]= true;
qx.push(x);
qy.push(y-1);
}
}
if (!seen[x-1][y]){
if (a[x-1][y] == 4){
dis11[x-1][y] = hight;
seen[x-1][y]= true;
qx.push(x-1);
qy.push(y);
}
}
}
int rah1to3(int x, int y, int hight){
if (a[x][y+1] == 3 || a[x][y-1] == 3 || a[x+1][y] == 3 || a[x-1][y] == 3){
r1to3 = hight;
return 1;
}else{
return 0;
}
}
int rah1to2(int x, int y, int hight){
if (a[x][y+1] == 2 || a[x][y-1] == 2 || a[x+1][y] == 2 || a[x-1][y] == 2){
r1to2 = hight;
return 1;
}else{
return 0;
}
}
int rah2to3(int x, int y, int hight){
if (a[x][y+1] == 3 || a[x][y-1] == 3 || a[x+1][y] == 3 || a[x-1][y] == 3){
r2to3 = hight;
return 1;
}else{
return 0;
}
}
void bfs1(int x, int y, int hight, int p){
if (p == 2){
if (rah1to2(x, y, hight) == 1){
// cout << "gooooooz" << '\n';
return;
}
}else if (p == 3){
if (rah1to3(x, y, hight) == 1){
// cout << "gooooooz" << '\n';
return;
}
}else if (p == 4){
if (rah2to3(x, y, hight) == 1){
// cout << "gooooooz" << '\n';
return;
}
}
hight++;
if (!seen[x][y+1]){
if (a[x][y+1] == 4){
dis1[x][y+1] = hight;
seen[x][y+1]= true;
qx.push(x);
qy.push(y+1);
}
}
if (!seen[x+1][y]){
if (a[x+1][y] == 4){
dis1[x+1][y] = hight;
seen[x+1][y]= true;
qx.push(x+1);
qy.push(y);
}
}
if (!seen[x][y-1]){
if (a[x][y-1] == 4){
dis1[x][y-1] = hight;
seen[x][y-1]= true;
qx.push(x);
qy.push(y-1);
}
}
if (!seen[x-1][y]){
if (a[x-1][y] == 4){
dis1[x-1][y] = hight;
seen[x-1][y]= true;
qx.push(x-1);
qy.push(y);
}
}
}
void chek1(int x, int y){
if (a[x][y+1] == 2){
moj12 = true;
}
if (a[x+1][y] == 2){
moj12 = true;
}
if (a[x-1][y] == 2){
moj12 = true;
}
if (a[x][y-1] == 2){
moj12 = true;
}
if (a[x][y+1] == 3){
moj13 = true;
}
if (a[x+1][y] == 3){
moj13 = true;
}
if (a[x-1][y] == 3){
moj13 = true;
}
if (a[x][y-1] == 3){
moj13 = true;
}
}
void check2(int x, int y){
if (a[x][y+1] == 3){
moj23 = true;
}
if (a[x+1][y] == 3){
moj23 = true;
}
if (a[x-1][y] == 3){
moj23 = true;
}
if (a[x][y-1] == 3){
moj23 = true;
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++){
string s;
cin >> s;
for (int j = 0; j < m; j++){
if (s[j] == '1'){
a[i][j+1] = 1;
g1x.push_back(i);
g1y.push_back(j+1);
}else if (s[j] == '2'){
a[i][j+1] = 2;
g2x.push_back(i);
g2y.push_back(j+1);
}else if (s[j] == '3'){
a[i][j+1] = 3;
g3x.push_back(i);
g3y.push_back(j+1);
}else if (s[j] == '.'){
a[i][j+1] = 4;
}else if (s[j] == '#'){
a[i][j+1] = 5;
}
}
}
for (int i = 0; i < g1x.size(); i++){
int x = g1x[i];
int y = g1y[i];
chek1(x, y);
}
for (int i = 0; i < g2y.size(); i++){
int x = g2x[i];
int y = g2y[i];
check2(x, y);
}
if (moj12 == true && moj13 == true){
cout << 0 << '\n';
}else if (moj12 == true && moj23 == true){
cout << 0 << '\n';
}else if (moj13 == true && moj23 == true){
cout << 0 << '\n';
}else if (moj12 == true){
for (int i = 0; i < g2x.size(); i++){
int x = g2x[i];
int y = g2y[i];
g1x.push_back(x);
g1y.push_back(y);
}
for (int i = 0; i < g1x.size(); i++){
int x = g1x[i];
int y = g1y[i];
dis1[x][y] = 0;
seen[x][y] = true;
qx.push(x);
qy.push(y);
}
while (qx.size()){
int x = qx.front();
int y = qy.front();
qx.pop();
qy.pop();
// cout << "x: " << x << " y: " << y << '\n';
bfs1(x, y, dis1[x][y], 3);
if (r1to3 > -1){
break;
}
}
cout << r1to3 << '\n';
}else if (moj13 == true){
for (int i = 0; i < g3x.size(); i++){
int x = g3x[i];
int y = g3y[i];
g1x.push_back(x);
g1y.push_back(y);
}
for (int i = 0; i < g1x.size(); i++){
int x = g1x[i];
int y = g1y[i];
dis1[x][y] = 0;
seen[x][y] = true;
qx.push(x);
qy.push(y);
}
while (qx.size()){
int x = qx.front();
int y = qy.front();
qx.pop();
qy.pop();
// cout << "x: " << x << " y: " << y << '\n';
bfs1(x, y, dis1[x][y], 2);
if (r1to2 > -1){
break;
}
}
cout << r1to2 << '\n';
// cout << "ihefehlkwf ";
}else if (moj23 == true){
// cout << "kikehfkuekd";
for (int i = 0; i < g3x.size(); i++){
int x = g3x[i];
int y = g3y[i];
a[x][y] = 2;
g2x.push_back(x);
g2y.push_back(y);
}
for (int i = 0; i < g1x.size(); i++){
int x = g1x[i];
int y = g1y[i];
dis1[x][y] = 0;
seen[x][y] = true;
qx.push(x);
qy.push(y);
}
while (qx.size()){
int x = qx.front();
int y = qy.front();
qx.pop();
qy.pop();
// cout << "x: " << x << " y: " << y << '\n';
bfs1(x, y, dis1[x][y], 2);
if (r1to2 > -1){
break;
}
}
cout << r1to2 << '\n';
}else{
for (int i = 0; i < g1x.size(); i++){
int x = g1x[i];
int y = g1y[i];
dis1[x][y] = 0;
seen[x][y] = true;
qx.push(x);
qy.push(y);
}
while (qx.size()){
int x = qx.front();
int y = qy.front();
qx.pop();
qy.pop();
// cout << "x: " << x << " y: " << y << '\n';
bfs1(x, y, dis1[x][y], 2);
if (r1to2 > -1){
break;
}
}
while (qx.size()){
qx.pop();
qy.pop();
}
// r1to2 == ok
memset(seen, 0, sizeof(seen));
memset(dis1, 0, sizeof(dis1));
for (int i = 0; i < g1x.size(); i++){
int x = g1x[i];
int y = g1y[i];
dis1[x][y] = 0;
seen[x][y] = true;
qx.push(x);
qy.push(y);
}
while (qx.size()){
int x = qx.front();
int y = qy.front();
qx.pop();
qy.pop();
// cout << "x: " << x << " y: " << y << '\n';
bfs1(x, y, dis1[x][y], 3);
if (r1to3 > -1){
break;
}
}
while (qx.size()){
qx.pop();
qy.pop();
}
// r1to3 == ok
memset(seen, 0, sizeof(seen));
memset(dis1, 0, sizeof(dis1));
for (int i = 0; i < g2x.size(); i++){
int x = g2x[i];
int y = g2y[i];
dis1[x][y] = 0;
seen[x][y] = true;
qx.push(x);
qy.push(y);
}
while (qx.size()){
int x = qx.front();
int y = qy.front();
qx.pop();
qy.pop();
// cout << "x: " << x << " y: " << y << '\n';
bfs1(x, y, dis1[x][y], 4);
if (r2to3 > -1){
break;
}
}
while (qx.size()){
qx.pop();
qy.pop();
}
memset(seen, 0, sizeof(seen));
memset(dis1, 0, sizeof(dis1));
// r1to3 == ok
for (int i = 0; i < g1x.size(); i++){
int x = g1x[i];
int y = g1y[i];
dis11[x][y] = 0;
seen[x][y] = true;
qx.push(x);
qy.push(y);
}
while (qx.size()){
int x = qx.front();
int y = qy.front();
qx.pop();
qy.pop();
// cout << "x: " << x << " y: " << y << '\n';
jafar(x, y, dis11[x][y]);
}
memset(seen, 0, sizeof(seen));
for (int i = 0; i < g2x.size(); i++){
int x = g2x[i];
int y = g2y[i];
dis2[x][y] = 0;
seen[x][y] = true;
qx.push(x);
qy.push(y);
}
while (qx.size()){
int x = qx.front();
int y = qy.front();
qx.pop();
qy.pop();
// cout << "x: " << x << " y: " << y << '\n';
hasan(x, y, dis2[x][y]);
}
memset(seen, 0, sizeof(seen));
for (int i = 0; i < g3x.size(); i++){
int x = g3x[i];
int y = g3y[i];
dis3[x][y] = 0;
seen[x][y] = true;
qx.push(x);
qy.push(y);
}
while (qx.size()){
int x = qx.front();
int y = qy.front();
qx.pop();
qy.pop();
// cout << "x: " << x << " y: " << y << '\n';
mamad(x, y, dis3[x][y]);
}
int d = 5000010;
if (r1to2 == -1 && r1to3 == -1 && r2to3 == -1){
cout << -1 << '\n';
}else if (r1to2 == -1 && r1to3 == -1 && r2to3 > -1){
cout << -1 << '\n';
}else if (r1to2 == -1 && r1to3 > -1 && r2to3 == -1){
cout << -1 << '\n';
}else if (r1to2 > -1 && r1to3 == -1 && r2to3 == -1){
cout << -1 << '\n';
}else{
if (r1to2 == -1){
r1to2 = 1000010;
}
if (r1to3 == -1){
r1to3 = 1000010;
}
if (r2to3 == -1){
r2to3 = 1000010;
}
d = min(d, r1to2+r1to3);
d = min(d, r1to2+r2to3);
d = min(d, r1to3+r2to3);
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
if (a[i][j] == 4){
if (dis11[i][j] > 0 && dis2[i][j] > 0 && dis3[i][j] > 0){
d = min(d, dis11[i][j]+dis2[i][j]+dis3[i][j]-2);
// cout << "sagtole " << i << " " << j << '\n';
// cout << " " << dis11[i][j] << " " << dis2[i][j] << " "<< dis3[i][j] << '\n';
}
}
}
}
cout << d << '\n';
}
}
}Editor is loading...