Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include <vector>
- #include <queue>
- #include <math.h>
- #include <algorithm>
- using namespace std;
- typedef pair<int, int> pii;
- vector<pii> o_stair1_que;
- vector<pii> o_stair2_que;
- queue<int> stair1;
- queue<int> stair2;
- vector<pii> person;
- vector<pii> stair;
- int fin_t[2];
- int map[11][11];
- int n;
- int n_person;
- int ans = 1e9;
- int calc_dist(int x1 , int y1, int x2, int y2)
- {
- return abs(x1 - x2) + abs(y1 - y2);
- }
- void init()
- {
- stair.clear();
- person.clear();
- o_stair1_que.clear();
- o_stair2_que.clear();
- while (!stair1.empty())
- {
- stair1.pop();
- }
- while (!stair2.empty())
- {
- stair2.pop();
- }
- memset(map, 0, sizeof(map));
- memset(fin_t, 0, sizeof(fin_t));
- }
- bool comparator(pii x, pii y)
- {
- return x.second < y.second;
- }
- void solve(int depth, int s)
- {
- if (depth == n_person)
- {
- int val1 = -1;
- int val2 = -1;
- bool waiting1[10];
- bool waiting2[10];
- memset(waiting1, false, sizeof(waiting1));
- memset(waiting2, false, sizeof(waiting2));
- if (!o_stair1_que.empty())
- {
- vector<pii> stair1_que;
- for (int i = 0; i < o_stair1_que.size(); i++)
- {
- stair1_que.push_back(make_pair(o_stair1_que[i].first, o_stair1_que[i].second));
- }
- sort(stair1_que.begin(), stair1_que.end(), comparator);
- int timE = 0;
- int n_stair1 = o_stair1_que.size();
- int fin_stair1 = 0;
- while (1)
- {
- vector<pii>::iterator iter;
- queue<int> temp;
- if (n_stair1 == fin_stair1)
- {
- break;
- }
- while (!stair1.empty())
- {
- if (stair1.front() != timE)
- {
- temp.push(stair1.front());
- }
- else
- {
- if (val1 < stair1.front())
- {
- val1 = stair1.front();
- }
- fin_stair1++;
- }
- stair1.pop();
- }
- while (!temp.empty())
- {
- stair1.push(temp.front());
- temp.pop();
- }
- for (iter = stair1_que.begin(); iter != stair1_que.end(); iter++)
- {
- if ((*iter).second == timE && stair1.size() < 3 && !waiting1[(*iter).first])
- {
- stair1.push((timE + 1) + fin_t[0]);
- }
- else if ((*iter).second == timE && stair1.size() < 3 && waiting1[(*iter).first])
- {
- stair1.push((timE)+fin_t[0]);
- }
- else if ((*iter).second == timE && stair1.size() == 3)
- {
- waiting1[(*iter).first] = true;
- (*iter).second = stair1.front();
- }
- }
- timE++;
- }
- }
- if (!o_stair2_que.empty())
- {
- vector<pii> stair2_que;
- for (int i = 0; i < o_stair2_que.size(); i++)
- {
- stair2_que.push_back(make_pair(o_stair2_que[i].first, o_stair2_que[i].second));
- }
- sort(stair2_que.begin(), stair2_que.end(), comparator);
- int timE = 0;
- int n_stair2 = o_stair2_que.size();
- int fin_stair2= 0;
- while (1)
- {
- vector<pii>::iterator iter;
- queue<int> temp;
- if (n_stair2 == fin_stair2)
- {
- break;
- }
- while (!stair2.empty())
- {
- if (stair2.front() != timE)
- {
- temp.push(stair2.front());
- }
- else
- {
- if (val2 < stair2.front())
- {
- val2 = stair2.front();
- }
- fin_stair2++;
- }
- stair2.pop();
- }
- while (!temp.empty())
- {
- stair2.push(temp.front());
- temp.pop();
- }
- for (iter = stair2_que.begin(); iter != stair2_que.end(); iter++)
- {
- if ((*iter).second == timE && stair2.size() < 3 && !waiting2[(*iter).first])
- {
- stair2.push((timE + 1) + fin_t[1]);
- }
- else if ((*iter).second == timE && stair2.size() < 3 && waiting2[(*iter).first])
- {
- stair2.push((timE) + fin_t[1]);
- }
- else if ((*iter).second == timE && stair2.size() == 3)
- {
- waiting2[(*iter).first] = true;
- (*iter).second = stair2.front();
- }
- }
- timE++;
- }
- }
- int max = 0;
- if (val1 > val2)
- {
- max = val1;
- }
- else
- {
- max = val2;
- }
- if (ans > max) ans = max;
- return;
- }
- //0번계단 이용
- int dist = calc_dist(person[depth].first, person[depth].second, stair[0].first, stair[0].second);
- o_stair1_que.push_back(make_pair(depth, dist));
- solve(depth + 1, 0);
- o_stair1_que.pop_back();
- //1번계단 이용
- dist = calc_dist(person[depth].first, person[depth].second, stair[1].first, stair[1].second);
- o_stair2_que.push_back(make_pair(depth, dist));
- solve(depth + 1, 1);
- o_stair2_que.pop_back();
- }
- int main(void)
- {
- //freopen("sample_input.txt", "r", stdin);
- int tc;
- scanf("%d", &tc);
- for (int t = 1; t <= tc; t++)
- {
- scanf("%d", &n);
- init();
- int idx = 0;
- ans = 1e9;
- for (int i = 1; i <= n; i++)
- {
- for (int j = 1; j <= n; j++)
- {
- int exist;
- scanf("%d", &exist);
- if (exist == 1)
- {
- person.push_back(make_pair(i, j));
- }
- if (exist > 1)
- {
- stair.push_back(make_pair(i, j));
- fin_t[idx++] = exist;
- }
- }
- }
- n_person = person.size();
- solve(0, 0);
- printf("#%d %d\n", t, ans);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement