Untitled
unknown
plain_text
2 years ago
14 kB
4
Indexable
###################################################
pizza v1
package practise;
import java.util.Scanner;
public class pizza_location {
static int rest, r2, idxr, idxp;
static int x = 0, y = 1, p = 2, ans;
static int[][] location, person, map;
static int[] choose;
private static void chooseRest(int a) {
if(a > rest) {
solve();
return;
}
for(int i = choose[a - 1] + 1; i < idxr; i++) {
choose[a] = i;
chooseRest(a + 1);
}
}
private static void solve() {
int tmp = 0;
for(int i = 0; i < idxp; i++) {
for(int j = 1; j <= rest; j++) {
if(map[choose[j]][i] != 0) {
tmp += map[choose[j]][i];
break;
}
}
}
if(ans < tmp) ans = tmp;
}
private static boolean calR(int ir, int ip) {
int dx = location[x][ir] - person[x][ip];
int dy = location[y][ir] - person[y][ip];
int d = dx * dx + dy * dy;
if(d <= r2) return true;
else return false;
}
private static void fillMap() {
for(int i = 0; i < idxr; i++) {
for(int j = 0; j < idxp; j++) {
if(calR(i, j)) {
map[i][j] = person[p][j];
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
for(int tc = 1; tc <= testcase; tc++) {
rest = sc.nextInt();
int r = sc.nextInt();; r2 = r * r;
idxr = sc.nextInt();
location = new int[2][idxr];
for(int i = 0; i < idxr; i++) {
location[x][i] = sc.nextInt();
location[y][i] = sc.nextInt();
}
idxp = sc.nextInt();
person = new int[3][idxp];
for(int i = 0; i < idxp; i++) {
person[x][i] = sc.nextInt();
person[y][i] = sc.nextInt();
person[p][i] = sc.nextInt();
}
map = new int[idxr][idxp];
fillMap();
ans = 0;
choose = new int[rest + 1];
choose[0] = -1;
chooseRest(1);
System.out.println("#" + tc + " " + ans);
}
}
}
###################################################
pizza v2
package practise;
import java.util.Scanner;
public class pizza_locationv2 {
static int rest, r2, idxr, idxp;
static int x = 0, y = 1, p = 2, ans;
static int[][] location, person;
static boolean[][] map;
static int[] choose;
static boolean[] visit;
private static boolean calR(int ir, int ip) {
int dx = location[x][ir] - person[x][ip];
int dy = location[y][ir] - person[y][ip];
int d = dx * dx + dy * dy;
if(d <= r2) return true;
else return false;
}
private static void fillMap() {
for(int i = 0; i < idxr; i++) {
for(int j = 0; j < idxp; j++) {
if(calR(i, j)) {
map[i][j] = true;
}
}
}
}
private static void solve(int loop) {
if(loop > idxr) return;
int sum = 0;
for(int i = 0; i < idxr; i++) {
sum += choose[i];
}
if(sum == rest) {
int cnt = 0;
for(int i = 0; i < idxp; i++) {
visit[i] = false;
}
for(int i = 0; i < idxr; i++) {
for(int j = 0; j < idxp; j++) {
if(choose[i] == 1 && visit[j] == false && map[i][j] == true) {
cnt += person[p][j];
visit[j] = true;
}
}
}
if(ans < cnt) ans = cnt;
return;
}
for(int i = 1; i >= 0; i--) {
choose[loop] = i;
solve(loop + 1);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
for(int tc = 1; tc <= testcase; tc++) {
rest = sc.nextInt();
int r = sc.nextInt();; r2 = r * r;
idxr = sc.nextInt();
location = new int[2][idxr];
for(int i = 0; i < idxr; i++) {
location[x][i] = sc.nextInt();
location[y][i] = sc.nextInt();
}
idxp = sc.nextInt();
person = new int[3][idxp];
for(int i = 0; i < idxp; i++) {
person[x][i] = sc.nextInt();
person[y][i] = sc.nextInt();
person[p][i] = sc.nextInt();
}
map = new boolean[idxr][idxp];
fillMap();
choose = new int[idxr + 1];
visit = new boolean[idxp];
ans = 0;
solve(0);
System.out.println("#" + tc + " " + ans);
}
}
}
############################################
pizza c++
#include <iostream>
using namespace std;
int k, r; // 1 <= k <= 10, 1 <= r <= 500
int m; // k <= m <= 20
int A[20][2];
int n; // 1 <= n <= 100
int B[100][3];
bool C[20][100];
int D[20];
bool Vis[100];
int res;
void inputF () {
cin >> k >> r;
cin >> m;
for (int i = 0; i < m; i++) {
cin >> A[i][0] >> A[i][1];
}
cin >> n;
for (int i = 0; i < n; i++) {
cin >> B[i][0] >> B[i][1] >> B[i][2];
}
}
void resetF () {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
C[i][j] = false;
}
}
for (int i = 0; i < m; i++) {
D[i] = 0;
}
res = 0;
}
void markF () {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (( (A[i][0] - B[j][0])*(A[i][0] - B[j][0]) + (A[i][1] - B[j][1])*(A[i][1] - B[j][1]) ) <= r*r) {
C[i][j] = true;
}
}
}
}
void pizzaF (int loop) {
if (loop > m) {
return;
}
int sum = 0;
for (int i = 0; i < m; i++) {
sum += D[i];
}
if (sum == k) {
int cnt = 0;
for (int i = 0; i < n; i++) {
Vis[i] = false;
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (D[i] == 1 && Vis[j] == false && C[i][j] == true) {
cnt += B[j][2];
Vis[j] = true;
}
}
}
if (res < cnt) {
res = cnt;
}
return;
}
for (int i = 1; i >= 0; i--) {
D[loop] = i;
pizzaF(loop+1);
}
}
int main () {
int TestCase;
cin >> TestCase;
for (int tc = 1; tc <= TestCase; tc++) {
inputF();
resetF();
markF();
pizzaF(0);
cout << "#" << tc << " " << res << endl;
}
return 0;
}
########################################################
frog v2
package practise;
import java.util.Scanner;
class MyQueue{
private int front, rear, max, cnt;
private int[] q;
public MyQueue(int a) {
// TODO Auto-generated constructor stub
front = 0;
rear = -1;
max = a;
cnt = 0;
q = new int[a];
}
public boolean isEmpty() {
return cnt == 0;
}
public void enqueue(int x) {
rear = (rear + 1) % max;
q[rear] = x;
++cnt;
}
public int dequeue()
{
int tmp = q[front];
front = (front + 1) % max;
--cnt;
return tmp;
}
}
public class the_frogv2 {
static int n;
static int x = 0, y = 1, r = 2, near = 40 * 40, far = 90 * 90, INF = 100000;
static int[] visit;
static int[][] map;
public static int calculate(int i1, int i2) {
int l1 = (map[x][i1] - map[x][i2]) * (map[x][i1] - map[x][i2]);
int l2 = (map[y][i1] - map[y][i2]) * (map[y][i1] - map[y][i2]);
int l3 = map[r][i1] * map[r][i1] + map[r][i2] * map[r][i2];
int len = l1 + l2 - l3;
if(len < near) {
return 1;
}
else {
if(len < far) {
return 200;
}
else return INF;
}
}
private static void BFS() {
MyQueue q = new MyQueue(n * n);
q.enqueue(0);
visit[0] = 0;
while(!q.isEmpty()) {
int x = q.dequeue();
for(int i = 0; i < n; i++) {
if(x != i) {
int tmp = calculate(x, i);
if(tmp + visit[x] < visit[i]) {
visit[i] = tmp + visit[x];
q.enqueue(i);
}
}
}
}
}
private static void reset() {
for(int i = 0; i < n; i++) {
visit[i] = INF;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
for(int tc = 1; tc <= testcase; tc++) {
n = sc.nextInt();
visit = new int[n];
map = new int[3][n];
for(int i = 0; i < n; i++) {
map[x][i] = sc.nextInt();
map[y][i] = sc.nextInt();
map[r][i] = sc.nextInt();
}
reset();
BFS();
int val = visit[n - 1];
if(val == INF) {
System.out.println(-1);
}
else {
System.out.println(val/200 + " " + val%200);
}
}
}
}
###############################################
frog v3 (backtrack)
package practise;
import java.util.Scanner;
public class the_frogv3 {
static int n, ansf, ansn;
static boolean flag;
static int x = 0, y = 1, r = 2, near = 40 * 40, far = 90 * 90, INF = 100000;
static boolean[] visit;
static int[][] map;
public static int calculate(int i1, int i2) {
int l1 = (map[x][i1] - map[x][i2]) * (map[x][i1] - map[x][i2]);
int l2 = (map[y][i1] - map[y][i2]) * (map[y][i1] - map[y][i2]);
int l3 = map[r][i1] * map[r][i1] + map[r][i2] * map[r][i2];
int len = l1 + l2 - l3;
if(len < near) {
return 1;
}
else {
if(len < far) {
return 2;
}
else return INF;
}
}
private static void solve(int leaf, int cntf, int cntn) {
if(leaf == n - 1) {
if(ansf > cntf) {
ansf = cntf;
ansn = cntn;
}
else if(ansf == cntf && ansn > cntn) {
ansn = cntn;
}
flag = true;
return;
}
for(int i = 1; i < n; i++) {
if(i != leaf && !visit[i]) {
int tmp = calculate(leaf, i);
if(tmp == 1) {
visit[i] = true;
solve(i, cntf, cntn + 1);
visit[i] = false;
}
else if(tmp == 2) {
visit[i] = true;
solve(i, cntf + 1, cntn);
visit[i] = false;
}
// else return;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
for(int tc = 1; tc <= testcase; tc++) {
n = sc.nextInt();
visit = new boolean[n];
map = new int[3][n];
for(int i = 0; i < n; i++) {
map[x][i] = sc.nextInt();
map[y][i] = sc.nextInt();
map[r][i] = sc.nextInt();
}
ansn = INF; ansf = INF;
flag = false;
visit[0] = true;
solve(0, 0, 0);
if(!flag) {
System.out.println(-1);
}
else {
System.out.println(ansf + " " + ansn);
}
}
}
}
############################################
cleaning robot
package practise;
import java.util.Scanner;
class Queue{
private int front, rear, max, cnt;
private int[] q;
public Queue(int a) {
// TODO Auto-generated constructor stub
front = 0;
rear = -1;
max = a;
cnt = 0;
q = new int[a];
}
public boolean isEmpty() {
return cnt == max;
}
public void enqueue(int a) {
rear = (rear + 1) % max;
q[rear] = a;
cnt++;
}
public int dequeue() {
int a = q[front];
front = (front + 1) % max;
cnt--;
return a;
}
}
public class cleaning_robot {
static int row, col, dirt, step, xr, yr;
static int[][] map;
static boolean[][] visit;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
for(int tc = 1; tc <= testcase; tc++) {
row = sc.nextInt(); col = sc.nextInt();
map = new int[row][col];
visit = new boolean[row][col];
dirt = 0; xr = 0; yr = 0;
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
map[i][j] = sc.nextInt();
if(map[i][j] == 1) {
dirt++;
}
else if(map[i][j] == 3) {
xr = i; yr = j;
}
}
}
}
}
}
######################################################
cleaning robot c++
#include <iostream>
using namespace std;
int N, M;
int a[105][105];
int visited[105][105];
int cnt[105][105];
int dx[] = {-1, 0, 1, 0};
int dy[] = { 0, 1, 0, -1};
int qx[100000];
int qy[100000];
int front;
int rear;
int done[105][105];
int cntDirty;
// Queue
bool isEmpty(){
return front == -1;
}
void push(int x, int y){
if(front == -1) front = 0;
rear++;
qx[rear] = x;
qy[rear] = y;
}
void pop(){
if(front >= rear) front = rear = -1;
else front++;
}
// BFS
int XDirty, YDirty;
int total;
int BFS(int x, int y){
front = rear = -1;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
visited[i][j] = 0;
cnt[i][j] = 0;
}
}
visited[x][y] = 1;
push(x,y);
int step = 1000000;
while(!isEmpty()){
int topx = qx[front];
int topy = qy[front];
pop();
for(int i = 0; i < 4; i++){
int x1 = topx + dx[i];
int y1 = topy + dy[i];
if(x1 >= 0 && x1 < N && y1 >= 0 && y1 < M && a[x1][y1] >= 0 && a[x1][y1] < 2 && visited[x1][y1] == 0){
cnt[x1][y1] = cnt[topx][topy] + 1;
visited[x1][y1] = 1;
push(x1,y1);
if(a[x1][y1] == 1 && done[x1][y1] == 0) {
if(cnt[x1][y1] < step){
step = cnt[x1][y1];
XDirty = x1;
YDirty = y1;
done[x1][y1] = 1;
}
}
}
}
}
return step;
}
void in(){
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cout << done[i][j];
}
cout << endl;
}
}
int main(){
int T; cin >> T;
for(int tc = 1; tc <= T; tc++){
cin >> N >> M;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
done[i][j] = 0;
}
}
cntDirty = 0; total = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> a[i][j];
if(a[i][j] == 1) cntDirty++;
if(a[i][j] == 3){
XDirty = i;
YDirty = j;
}
}
}
done[XDirty][YDirty] = 3;
for(int i = 0; i < cntDirty; i++){
a[XDirty][YDirty] = 0;
total += BFS(XDirty, YDirty);
}
cout << "Case #" << tc << endl;
if(total >= 1000000){
cout << -1 << endl;
}else{
cout << total << endl;
}
}
return 0;
}
Editor is loading...