Untitled
user_5152005
plain_text
6 months ago
8.2 kB
2
Indexable
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <queue>
#include <stack>
#include <math.h>
#include <iomanip>
#include <algorithm>
#define ROAD 46
#define START 115
#define START_A 115
#define START_B 116
#define FLAG 102
#define FLAG_1 102
#define FLAG_2 103
#define FLAG_3 104
#define FLAG_4 105
#define FLAG_5 106
#define FLAG_6 107
#define FLAG_7 108
#define FLAG_8 109
#define FLAG_9 110
#define FLAG_10 111
#define oo 1000000
using namespace std;
int R, C, total_flag;
int map[1001][1001];
int visited[1001][1001];
int adj[200][200];
int taken[11];
int flag_r[11];
int flag_c[11];
int start_r_A;
int start_c_A;
int start_r_B;
int start_c_B;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
int min_time;
int min_diff;
int total_flag_A;
int total_flag_B;
void nhapmap()
{
int count1 = 0;
int count2 = 1;
for (size_t i = 1; i <= R; i++)
{
for (size_t j = 1; j <= C; j++)
{
char temp;
cin >> temp;
map[i][j] = (int)temp;
if (map[i][j] == START)
{
if (count1 == 0)
{
start_r_A = i;
start_c_A = j;
count1++;
}
else
{
start_r_B = i;
start_c_B = j;
map[i][j] = START_B;
}
}
if (map[i][j] == FLAG)
{
if (count2 == 1)
{
flag_r[count2] = i;
flag_c[count2] = j;
map[i][j] = FLAG_1;
count2++;
}
else if (count2 == 2)
{
flag_r[count2] = i;
flag_c[count2] = j;
map[i][j] = FLAG_2;
count2++;
}
else if (count2 == 3)
{
flag_r[count2] = i;
flag_c[count2] = j;
map[i][j] = FLAG_3;
count2++;
}
else if (count2 == 4)
{
flag_r[count2] = i;
flag_c[count2] = j;
map[i][j] = FLAG_4;
count2++;
}
else if (count2 == 5)
{
flag_r[count2] = i;
flag_c[count2] = j;
map[i][j] = FLAG_5;
count2++;
}
else if (count2 == 6)
{
flag_r[count2] = i;
flag_c[count2] = j;
map[i][j] = FLAG_6;
count2++;
}
else if (count2 == 7)
{
flag_r[count2] = i;
flag_c[count2] = j;
map[i][j] = FLAG_7;
count2++;
}
else if (count2 == 8)
{
flag_r[count2] = i;
flag_c[count2] = j;
map[i][j] = FLAG_8;
count2++;
}
else if (count2 == 9)
{
flag_r[count2] = i;
flag_c[count2] = j;
map[i][j] = FLAG_9;
count2++;
}
else if (count2 == 10)
{
flag_r[count2] = i;
flag_c[count2] = j;
map[i][j] = FLAG_10;
count2++;
}
}
}
}
}
int inBound(int a, int b)
{
if (1 <= a && a <= R && 1 <= b && b <= C)
{
return 1;
}
return 0;
}
void resetVisited()
{
for (size_t i = 0; i <= R; i++)
{
for (size_t j = 0; j <= C; j++)
{
visited[i][j] = 0;
}
}
}
void BFS(int start_x, int start_y)
{
queue<pair<int, int>>q;
q.push({ start_x, start_y });
visited[start_x][start_y] = 1;
while (!q.empty())
{
int old_x = q.front().first;
int old_y = q.front().second;
q.pop();
for (size_t k = 0; k < 4; k++)
{
int new_x = old_x + dx[k];
int new_y = old_y + dy[k];
if (visited[new_x][new_y] == 0 && inBound(new_x, new_y))
{
visited[new_x][new_y] = 1 + visited[old_x][old_y];
if (map[new_x][new_y] == FLAG_1)
{
adj[map[start_x][start_y]][FLAG_1] = visited[old_x][old_y];
adj[FLAG_1][map[start_x][start_y]] = visited[old_x][old_y];
}
else if (map[new_x][new_y] == FLAG_2)
{
adj[map[start_x][start_y]][FLAG_2] = visited[old_x][old_y];
adj[FLAG_2][map[start_x][start_y]] = visited[old_x][old_y];
}
else if (map[new_x][new_y] == FLAG_3)
{
adj[map[start_x][start_y]][FLAG_3] = visited[old_x][old_y];
adj[FLAG_3][map[start_x][start_y]] = visited[old_x][old_y];
}
else if (map[new_x][new_y] == FLAG_4)
{
adj[map[start_x][start_y]][FLAG_4] = visited[old_x][old_y];
adj[FLAG_4][map[start_x][start_y]] = visited[old_x][old_y];
}
else if (map[new_x][new_y] == FLAG_5)
{
adj[map[start_x][start_y]][FLAG_5] = visited[old_x][old_y];
adj[FLAG_5][map[start_x][start_y]] = visited[old_x][old_y];
}
else if (map[new_x][new_y] == FLAG_6)
{
adj[map[start_x][start_y]][FLAG_6] = visited[old_x][old_y];
adj[FLAG_6][map[start_x][start_y]] = visited[old_x][old_y];
}
else if (map[new_x][new_y] == FLAG_7)
{
adj[map[start_x][start_y]][FLAG_7] = visited[old_x][old_y];
adj[FLAG_7][map[start_x][start_y]] = visited[old_x][old_y];
}
else if (map[new_x][new_y] == FLAG_8)
{
adj[map[start_x][start_y]][FLAG_8] = visited[old_x][old_y];
adj[FLAG_8][map[start_x][start_y]] = visited[old_x][old_y];
}
else if (map[new_x][new_y] == FLAG_9)
{
adj[map[start_x][start_y]][FLAG_9] = visited[old_x][old_y];
adj[FLAG_9][map[start_x][start_y]] = visited[old_x][old_y];
}
else if (map[new_x][new_y] == FLAG_10)
{
adj[map[start_x][start_y]][FLAG_10] = visited[old_x][old_y];
adj[FLAG_10][map[start_x][start_y]] = visited[old_x][old_y];
}
q.push({ new_x,new_y });
}
}
}
}
int abs(int x)
{
return x > 0 ? x : -x;
}
void backtrack(int taken_flag_A, int taken_flag_B, int last_flag_A, int last_flag_B, int time_of_A, int time_of_B)
{
if (time_of_A + time_of_B > min_time)
{
return;
}
if (time_of_A + time_of_B +adj[last_flag_A][START_A] +adj[last_flag_B][START_B] > min_time)
{
return;
}
if (taken_flag_A == total_flag_A && taken_flag_B == total_flag_B)
{
if (time_of_A + time_of_B + adj[last_flag_A][START_A] + adj[last_flag_B][START_B] == min_time)
{
min_diff = abs(0 - time_of_A + time_of_B - adj[last_flag_A][START_A] + adj[last_flag_B][START_B]) < min_diff
? abs(0 - time_of_A + time_of_B - adj[last_flag_A][START_A] + adj[last_flag_B][START_B])
: min_diff;
}
else if (time_of_A + time_of_B + adj[last_flag_A][START_A] + adj[last_flag_B][START_B] < min_time)
{
min_time = time_of_A + time_of_B + adj[last_flag_A][START_A] + adj[last_flag_B][START_B];
min_diff = abs( 0 - time_of_A + time_of_B - adj[last_flag_A][START_A] + adj[last_flag_B][START_B]);
}
return;
}
if (taken_flag_A != total_flag_A)
{
for (size_t i = 1; i <= total_flag; i++)
{
if (taken[i] == 0)
{
taken[i] = 1;
backtrack(1 + taken_flag_A, taken_flag_B, map[flag_r[i]][flag_c[i]], last_flag_B, time_of_A + adj[last_flag_A][map[flag_r[i]][flag_c[i]]], time_of_B);
taken[i] = 0;
}
}
}
if (taken_flag_B != total_flag_B)
{
for (size_t i = 1; i <= total_flag; i++)
{
if (taken[i] == 0)
{
taken[i] = 1;
backtrack(taken_flag_A, taken_flag_B + 1, last_flag_A, map[flag_r[i]][flag_c[i]], time_of_A, time_of_B + adj[last_flag_B][map[flag_r[i]][flag_c[i]]]);
taken[i] = 0;
}
}
}
}
void solve()
{
for (size_t i = 0; i <= total_flag; i++)
{
//backtrack();
total_flag_B = i;
total_flag_A = total_flag - i;
backtrack(0, 0, START_A, START_B, 0, 0);
}
}
int main() {
freopen("input.txt", "r", stdin);
cin >> R >> C >> total_flag;
nhapmap();
BFS(start_r_A, start_c_A);
resetVisited();
BFS(start_r_B, start_c_B);
for (size_t i = 1; i <= total_flag; i++)
{
resetVisited();
BFS(flag_r[i], flag_c[i]);
}
min_time = oo;
min_diff = oo;
solve();
cout << min_time << " " << min_diff;
return 0;
}
Editor is loading...
Leave a Comment