Skip to content

Instantly share code, notes, and snippets.

@oskimura
Last active February 6, 2020 04:53
Show Gist options
  • Save oskimura/dfc23d56f203417b28320defcb2ccc47 to your computer and use it in GitHub Desktop.
Save oskimura/dfc23d56f203417b28320defcb2ccc47 to your computer and use it in GitHub Desktop.
// Maze Master
#include <iostream>
#include <vector>
#include <math.h>
#include <string>
#include <map>
#include <stdio.h>
#include <string.h>
#include <initializer_list>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <queue>
#include <set>
using namespace std;
const int INF = 1 << 29;
int main ()
{
int H,W;
cin >> H >> W;
char S[20][20];
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
cin >> S[i][j];
}
}
int dp[20][20][20][20];
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
for (int k = 0; k < H; k++) {
for (int l = 0; l < W; l++) {
dp[i][j][k][l] = INF;
if (i == k && j == l) {
dp[i][j][k][l] = 0;
}
}
}
}
}
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (S[i][j] == '#') {
continue;
}
for (int k = 0; k < 4; k++) {
int nx = dx[k] + j;
int ny = dy[k] + i;
if (nx < 0 || ny < 0 || nx >= W || ny >= H) {
continue;
}
if (S[ny][nx] == '#') {
continue;
}
dp[ny][nx][i][j] = dp[i][j][ny][nx] = 1;
}
}
}
int cost = 0;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
for (int k = 0; k < H; k++) {
for (int l = 0; l < W; l++) {
for (int m = 0; m < H; m++) {
for (int n = 0; n < W; n++) {
dp[k][l][m][n] = min(dp[k][l][m][n], dp[k][l][i][j] + dp[i][j][m][n]);
}
}
}
}
}
}
/*
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
for (int k = 0; k < H; k++) {
for (int l = 0; l < W; l++) {
cout << dp[i][j][k][l] << " ";
}
}
cout << endl;
}
}
*/
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
for (int k = 0; k < H; k++) {
for (int l = 0; l < W; l++) {
if (dp[i][j][k][l] < INF) {
cost = max(cost, dp[i][j][k][l]);
}
}
}
}
}
cout << cost << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment