Untitled
unknown
plain_text
a year ago
9.6 kB
7
Indexable
Gold,Fire,Ads,Ship
//HugoDaoVang
#include<iostream>
using namespace std;
#define MAX_INT 100000007
int t, tc, n, m, rear, front;
int a[21][21], vX[5], vY[5], qX[500], qY[500], visited[5][21][21], ans, max_kc, dem;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0 , -1};
void initQueue() {
rear = front = -1;
}
int isEmpty() {
if(front == rear) return 1;
return 0;
}
void enQueue(int x, int y) {
rear++;
qX[rear] = x;
qY[rear] = y;
}
int deQueueX() {
if(!isEmpty()) return qX[front + 1];
return -1;
}
int deQueueY() {
if(!isEmpty()) {
front++;
return qY[front];
}
return -1;
}
void BFS(int v, int i, int j) {
initQueue();
visited[v][i][j] = 1;
enQueue(i, j);
int x, y, tx, ty;
while(!isEmpty()) {
x = deQueueX();
y = deQueueY();
for(int k = 0; k < 4; k++) {
tx = x + dx[k];
ty = y + dy[k];
if(tx > 0 && tx <= n && ty > 0 && ty <= n && visited[v][tx][ty] == 0 && a[tx][ty] != 0) {
enQueue(tx, ty);
visited[v][tx][ty] = visited[v][x][y] + 1;
}
}
}
}
int main() {
freopen("input.txt", "r", stdin);
cin >> t;
for(tc = 1; tc <= t; tc++) {
cin >> n >> m;
int i, j, x;
for(i = 1; i <= m; i++) {
cin >> vX[i];
cin >> vY[i];
}
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
for(x = 1; x <= m; x++) {
a[vX[x]][vY[x]] = 2;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++) visited[x][i][j] = 0;
}
for(i = 1; i <= m; i++) {
BFS(i, vX[i], vY[i]);
}
ans = MAX_INT;
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
if(a[i][j] == 1) {
max_kc = 0;
dem = 0;
for(x = 1; x <= m; x++) {
if(visited[x][i][j]) dem++;
if(max_kc < visited[x][i][j]) max_kc = visited[x][i][j];
}
if(dem == m && ans > max_kc) ans = max_kc;
}
}
}
if(ans == MAX_INT) {
cout << "Case #" << tc << endl;
cout << -1 << endl;
} else {
cout << "Case #" << tc << endl;
cout << ans - 1 << endl;
}
}
return 0;
}
//Hugo Fire
#include <iostream>
using namespace std;
int N; // so hang
int M; // so cot
int SX, SY; //start row, start column
int numFire, xFire[300],yFire[300] ,start, last;
int numLake, xLake[225], yLake[225];
int numExit, xExit[225], yExit[225];
int dinamond[20][20], fire[20][20], lake[20][20], gate[20][20];
int maxtime, ans;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int visited[20][20];
void BFS()
{
int x, y, xNext, yNext;
for(int i = 0; i < last; i++)
{
fire[xFire[i]][yFire[i]] = 1;
}
while(start != last)
{
x = xFire[start];
y = yFire[start++];
for(int i = 0; i < 4; i++)
{
xNext = x + dx[i];
yNext = y + dy[i];
if(xNext >= 1 && xNext <= N && yNext >= 1 && yNext <= M)
{
if(lake[xNext][yNext] == 0 && (fire[xNext][yNext] == 0 || fire[xNext][yNext] > fire[x][y] + 1))
{
fire[xNext][yNext] = fire[x][y] + 1;
xFire[last] = xNext;
yFire[last++] = yNext;
}
}
}
}
}
void BT(int time, int score, int x, int y)
{
//cout << x << "\t" << y << endl;
visited[x][y] = 1;
if(gate[x][y] == 1)
{
if(score > ans)
ans = score;
}
for(int i = 0; i < 4; i++)
{
int xNext = x + dx[i];
int yNext = y + dy[i];
if(xNext >= 1 && xNext <= N && yNext >= 1 && yNext <= M)
{
if(visited[xNext][yNext] == 0)
{
if(lake[xNext][yNext] == 1)
BT(time+2, score + dinamond[xNext][yNext], xNext, yNext);
else if (fire[xNext][yNext] == 0 ||fire[xNext][yNext] > time + 1)
BT(time+1, score + dinamond[xNext][yNext], xNext, yNext);
}
}
}
visited[x][y] = 0;
}
int main()
{
freopen("input.txt", "r", stdin);
int T;
cin >> T;
for(int tc = 1; tc <= T; tc++)
{
ans = -1;
maxtime = 1;
start = 0;
last = 0;
cin >> N >> M >> SX >> SY;
cin >> numFire;
for(int i = 0; i < numFire; i++)
{
cin >> xFire[last];
cin >> yFire[last++];
}
cin >> numLake;
for (int i = 0; i < numLake; i++)
cin >> xLake[i] >> yLake[i];
cin >> numExit;
for(int i = 0; i < numExit; i++)
cin >> xExit[i] >> yExit[i];
for(int i = 1; i <= N; i++)
for(int j = 1; j <= M; j++)
{
cin >> dinamond[i][j];
fire[i][j] = 0;
lake[i][j] = 0;
gate[i][j] = 0;
visited[i][j] = 0;
}
for(int i = 0; i < numFire; i++)
fire[xFire[i]][yFire[i]] = 1;
for(int i = 0; i < numLake; i++)
lake[xLake[i]][yLake[i]] = 1;
for(int i = 0; i < numExit; i++)
gate[xExit[i]][yExit[i]] = 1;
BFS();
maxtime = 0;
for(int i = 0; i < numExit; i++)
if(maxtime < fire[xExit[i]][yExit[i]]) maxtime = fire[xExit[i]][yExit[i]];
BT(1, dinamond[SX][SY], SX, SY);
cout << "Case #" << tc << endl << ans << endl;
}
return 0;
}
//Hugo DiTau
#include<iostream>
using namespace std;
int tc, n, door1, cntTrain, currTrain;
int atrain[3][3], ghe[2][61];
int dx[] = {
-1,
1
};
int absx(int k) {
return k > 0 ? k : k * -1;
}
void lenTau(int dir, int k1) {
currTrain = 0;
int cnt = atrain[2][k1];
while(cnt > 0) {
int x = atrain[1][k1];
if(ghe[0][x] == 0) {
ghe[0][x] = 1;
ghe[1][x] = k1 + 1;
currTrain += 1;
//kx++;
cnt--;
if(!cnt) return;
}
for(int l = 1;; l++) {
if(dir == 1) {
for(int k = 0; k < 2; k++) {
int x2 = x + dx[k] * l;
if(x2 > 0 && x2 <= n && ghe[0][x2] == 0) {
ghe[0][x2] = absx(x2 - x) + 1;
ghe[1][x2] = k1 + 1;
currTrain += absx(x2 - x) + 1;
cnt--;
if(!cnt) return;
}
}
} else {
for(int k = 1; k >= 0; k--) {
int x2 = x + dx[k] * l;
if(x2 > 0 && x2 <= n && ghe[0][x2] == 0) {
ghe[0][x2] = absx(x2 - x) + 1;
ghe[1][x2] = k1 + 1;
currTrain += absx(x2 - x) + 1;
cnt--;
if(!cnt) return;
}
}
}
}
}
}
void xuongTau(int k) {
int cnt = atrain[2][k];
for(int i = 0; i <= n; i++) {
if(ghe[1][i] == k + 1) {
ghe[0][i] = 0;
ghe[1][i] = 0;
cnt--;
if(!cnt) return;
}
}
}
void backtrack(int door, int curr) {
if(!door) {
cntTrain = min(cntTrain, curr);
return;
}
for(int i = 0; i < 3; i++) {
if(atrain[0][i] == 1) {
for(int k1 = 1; k1 <= 2; k1++) {
lenTau(k1, i);
atrain[0][i] = 0;
backtrack(door - 1, curr + currTrain);
xuongTau(i);
atrain[0][i] = 1;
}
}
}
}
int main() {
freopen("input.txt", "r", stdin);
cin >> tc;
for(int t = 1; t <= tc; t++) {
cin >> n;
for(int i = 0; i < 3; i++) {
cin >> atrain[1][i] >> atrain[2][i];
atrain[0][i] = 1;
}
door1 = 3;
cntTrain = 1000;
backtrack(door1, 0);
cout << "Case #" << t << endl << cntTrain << endl;
}
return 0;
}
//xeplich quang cao
#include <iostream>
using namespace std;
int N, ans;
int timeAds[3], pointAds[3];
int visit[3], beginAds[3], endAds[3], cur_point[3];
int arrive[55], duration[55];
void nhap() {
cin >> N;
for(int i = 0; i < 3; i++) {
cin >> timeAds[i];
}
for(int i = 0; i < 3; i++) {
cin >> pointAds[i];
}
for(int i = 0; i < N; i++) {
cin >> arrive[i] >> duration[i];
}
}
void sum(int k) {
int sum = 0;
for(int i = 0; i < N; i++) {
int point = 0;
for(int j = 0; j < k; j++) {
if(arrive[i] <= beginAds[j] && arrive[i] + duration[i] >= endAds[j]) {
if(cur_point[j] > point) {
point = cur_point[j];
}
}
}
sum += point;
}
if(sum > ans) {
ans = sum;
}
}
void backtrack(int time, int k) {
if(time > 50 || k == 3) {
sum(k);
return;
}
backtrack(time + 1, k);
for(int i = 0; i < 3; i++) {
if(!visit[i]) {
visit[i] = 1;
beginAds[k] = time;
endAds[k] = time + timeAds[i];
cur_point[k] = pointAds[i];
backtrack(endAds[k], k + 1);
visit[i] = 0;
}
}
}
int main() {
freopen("INP.txt", "r", stdin);
int T;
cin >> T;
for(int tc = 1; tc <= T; tc++) {
nhap();
ans = 0;
backtrack(1, 0);
cout << "Case #" << tc << endl;
cout << ans << endl;
}
return 0;
}
//HugoGiaoHang
#include <iostream>
using namespace std;
int T, Sx, Sy, Hx, Hy, N, res, ans;
int place[3][15];
int dis[15][15];
bool visit[15];
//int hoanvi[12];
void nhap() {
cin >> Sx >> Sy >> Hx >> Hy;
cin >> N;
for(int i = 0; i <= N; i++) {
visit[i] = true;
}
place[0][0] = Sx;
place[1][0] = Sy;
place[0][N + 1] = Hx;
place[1][N + 1] = Hy;
for(int i = 1; i <= N; i++) {
int x, y;
cin >> x >> y;
place[0][i] = x;
place[1][i] = y;
}
int h = N + 1;
for(int i = 1; i <= N; i++) {
int x = place[0][h] > place[0][i] ? (place[0][h] - place[0][i]) : (place[0][i] - place[0][h]);
int y = place[1][h] > place[1][i] ? (place[1][h] - place[1][i]) : (place[1][i] - place[1][h]);
dis[i][h] = x + y;
}
for(int i = 0; i < N; i++) {
for(int j = i + 1; j <= N; j++) {
int x = place[0][i] > place[0][j] ? (place[0][i] - place[0][j]) : (place[0][j] - place[0][i]);
int y = place[1][i] > place[1][j] ? (place[1][i] - place[1][j]) : (place[1][j] - place[1][i]);
dis[i][j] = x + y;
dis[j][i] = dis[i][j];
}
}
}
void backtrack(int x, int tmp) {
if(ans > res) return;
for(int i = 1; i <= N; i++) {
if(visit[i]) {
visit[i] = false;
// hoanvi[x] = dis[tmp][i];
ans += dis[tmp][i];
if(x == N) {
int tmp = ans + dis[i][N + 1];
if(tmp < res) res = tmp;
} else backtrack(x + 1, i);
ans -= dis[tmp][i];
visit[i] = true;
}
}
}
int main() {
freopen("INP.txt", "r", stdin);
cin >> T;
for(int tc = 1; tc <= T; tc++) {
nhap();
res = 10000000;
ans = 0;
backtrack(1, 0);
cout << "Case #" << tc << " " << res << endl;
}
return 0;
}
Editor is loading...
Leave a Comment