挑战程序竞赛系列（32）：4.5 A*与IDA*

POJ 3523: The morning after Halloween

• 定义状态（3个ghost所处的位置）
• 生成下一状态
• 判断是否合法
• 合法加入队列
• 直到搜到最终状态

```    static final int INF = 1 << 29;
static final int[][] direction = {{1, 0},{-1, 0},{0, 1},{0, -1}, {0, 0}};
int W;
int H;
int[] dist = new int[256 * 256 * 256];
int[][] d = new int[3][256];
void solve() {
while (true){
int w = ni();
int h = ni();
int n = ni();

W = w;
H = h;

if (w + h + n == 0) break;
char[][] board = new char[h][w];
for (int i = 0; i < h; ++i){
for (int j = 0; j < w; ++j){
board[i][j] = nc();
}
}

//初始状态
int init = 0;
int goal = 0;

for (int i = 0; i < h; ++i){
for (int j = 0; j < w; ++j){
if (Character.isLowerCase(board[i][j])){
int pos = board[i][j] - 'a';
init |= ((i << 4) | j) << (pos * 8);
board[i][j] = ' ';
}
if (Character.isUpperCase(board[i][j])){
int pos = board[i][j] - 'A';
goal |= ((i << 4) | j) << (pos * 8);
board[i][j] = ' ';
}
}
}

d = new int[3][256];
for (int i = 0; i < 3; ++i) Arrays.fill(d[i], INF);
for (int i = 0; i < n; ++i){
int v = stateToVerties(goal, i);
Node start = new Node(v, 0);
d[i][v] = 0;
Queue<Node> queue = new PriorityQueue<Node>();
queue.offer(start);
while (!queue.isEmpty()){
Node now = queue.poll();
int row = now.v / 16;
int col = now.v % 16;
for (int[] dir : direction){
int nrow = row + dir[0];
int ncol = col + dir[1];
int nv = nrow * 16 + ncol;
if (nrow >= 0 && nrow < h && ncol >= 0 && ncol < w && board[nrow][ncol] != '#'
&& d[i][now.v] + 1 < d[i][nv]) {
d[i][nv] = d[i][now.v] + 1;
queue.offer(new Node(nv, d[i][nv]));
}
}
}
}

State start = new State(init, 0);
State end = new State(goal, 0);
dist = new int[256 * 256 * 256];
Arrays.fill(dist, INF);
dist[start.s] = 0;
Queue<Node> queue = new PriorityQueue<Node>();
queue.offer(new Node(start.s, 0));
int ans = -1;
while (!queue.isEmpty()){
Node now = queue.poll();
if (now.v == end.s){
ans = dist[now.v];
break;
}

int cost = now.d - hstar(now.v, d, n);
if (cost > dist[now.v]) continue;

List<State> nextStates = moveNext(new State(now.v, dist[now.v]), board, n);
for (State state : nextStates){
int next = state.s;
if (dist[next] > dist[now.v] + 1){
dist[next] = dist[now.v] + 1;
queue.offer(new Node(next, dist[next] + hstar(next, d, n)));
}
}
}

out.println(ans);
}
}

public int hstar(int state, int[][] d, int n){ //计算当前状态到终态的最短距离
int dist = 0;
for (int i = 0; i < n; ++i){
int sv = stateToVerties(state, i);
dist = Math.max(dist, d[i][sv]);
}
return dist;
}

class State{
int s;
int turn;

public State(int s, int turn){
this.s = s;
this.turn = turn;
}
}

public List<State> moveNext(State now, char[][] board, int n){
List<State>[] states = new ArrayList[n];
for (int i = 0; i < n; ++i) states[i] = new ArrayList<State>();

for (int i = 0; i < n; ++i){
int v = stateToVerties(now.s, i);
int row = v / 16;
int col = v % 16;
for (int[] dir : direction){
int nrow = row + dir[0];
int ncol = col + dir[1];
if (nrow >= 0 && nrow < H && ncol >= 0 && ncol < W && board[nrow][ncol] != '#'){
State state = new State(ghostToState(nrow, ncol, i),now.turn + 1);
}
}
}

//check 三种非法状态， 1. 撞墙 （在生成状态时已经避免） 2. 重合  3. 交换
List<State> validState = new ArrayList<State>();
for (int i = 0; 0 < n && i < states[0].size(); ++i){
int state = states[0].get(i).s;
int turn = states[0].get(i).turn;
for (int j = 0; 1 < n && j < states[1].size(); ++j){
state = states[0].get(i).s;
state |= states[1].get(j).s;
for (int l = 0; 2 < n && l < states[2].size(); ++l){
state = states[0].get(i).s;
state |= states[1].get(j).s;
state |= states[2].get(l).s;
if (3 == n && valid(state, now.s, n)) validState.add(new State(state, turn));
}
if (2 == n && valid(state, now.s, n)) validState.add(new State(state, turn));
}
if (1 == n) validState.add(new State(state, turn));
}
return validState;
}

public boolean valid(int state, int prev, int n){
int i = state >> 16 & (0xff);
int j = state >>  8 & (0xff);
int k = state >>  0 & (0xff);
if (n == 2 && (j == k)) return false;
if (n == 3 && (i == j || j == k || k == i)) return false; //重合
if (n == 2){
int pj = prev >> 8 & (0xff);
int pk = prev >> 0 & (0xff);
if (pj == k && pk == j) return false;
}
if (n == 3){
int pi = prev >> 16 & (0xff);
int pj = prev >>  8 & (0xff);
int pk = prev >>  0 & (0xff);
if (swap(i, j, pi, pj) || swap(i, k, pi, pk) || swap(j, k, pj, pk)) return false; //交换
}
return true;
}

public boolean swap(int i, int j, int pi, int pj){
return (i == pj) && (j == pi);
}

public int ghostToState(int i, int j, int id){
int state = 0;
state = (i << 4 | j) << (id * 8);
return state;
}

public int stateToVerties(int state, int n){
int ss = state >> (8 * n) & (0xff);
int si = ss >> 4;
int sj = ss & (0x0f);
return si * 16 + sj;
}

class Node implements Comparable<Node>{
int v;
int d;
public Node(int v, int d){
this.v = v;
this.d = d;
}
@Override
public int compareTo(Node that) {
return this.d - that.d;
}
}```

POJ 2032: Square Carpets

```import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;

public class Main{
InputStream is;
PrintWriter out;
String INPUT = "./data/judge/201708/P2032.txt";

static final int MAX_N = 10;
int ans, H, W, limit, max_W;
int[][] T; //以(x,y)为右下角的正方形最大边长
int[][] F; //输入
int[][] X; // 每个点被几个正方形覆盖
List<int[]> candicates;

void solve() {
while (true){
int w = ni();
int h = ni();
if (w + h == 0) break;

W = w;
H = h;
F = new int[MAX_N][MAX_N]; //输入
for (int i = 0; i < h; ++i){
for (int j = 0; j < w; ++j){
F[i][j] = ni();
}
}

//初始化
init();
out.println(idaStar() + ans);
}
}

void init(){
ans = 0;
max_W = 0;
T = new int[MAX_N][MAX_N]; //以(x,y)为右下角的正方形最大边长
X = new int[MAX_N][MAX_N]; // 每个点被几个正方形覆盖
candicates = new ArrayList<int[]>();

//统计每个顶点可覆盖的最大宽度
for (int i = 0; i < W; ++i){
T[0][i] = F[0][i];
}
for (int j = 0; j < H; ++j){
T[j][0] = F[j][0];
}

for (int i = 1; i < H; ++i){
for (int j = 1; j < W; ++j){
if (F[i][j] != 0){
T[i][j] = Math.min(Math.min(T[i - 1][j], T[i][j - 1]), T[i - 1][j - 1]) + 1;
}
}
}
//删除完全覆盖的正方形
for (int i = 0; i < H; ++i){
for (int j = 0; j < W; ++j){
if (T[i][j] != 0){
int len = T[i][j];
for (int k = 0; k < len; ++k){
for (int l = 0; l < len; ++l){
if (k == 0 && l == 0) continue;
if (i - k >= 0 && j - l >= 0 && T[i - k][j - l] + Math.max(l, k) <= T[i][j]){ //完全包含，则排除
T[i - k][j - l] = 0;
}
}
}
}
}
}

int[][] K = new int[MAX_N][MAX_N]; //每个点被几个正方形覆盖
for (int i = 0; i < H; ++i){
for (int j = 0; j < W; ++j){
if (T[i][j] != 0){
int t = T[i][j];
for (int l = 0; l < t; ++l){
for (int k = 0; k < t; ++k){
K[i - l][j - k] ++;
}
}
}
}
}

for (int i = 0; i < H; ++i){
for (int j = 0; j < W; ++j){
outer:
if (T[i][j] != 0){
int t = T[i][j];
for (int l = 0; l < t; ++l){
for (int k = 0; k < t; ++k){
if (K[i - l][j - k] == 1){
for (int x = 0; x < t; ++x){
for (int y = 0; y < t; ++y){
X[i - x][j - y] ++;
}
}
ans ++;
T[i][j] = 0;
break outer;
}
}
}
}
}
}

for (int i = H - 1; i >= 0; --i){
for (int j = W - 1; j >= 0; --j){
if (T[i][j] != 0){
max_W = Math.max(max_W, T[i][j]);
}
}
}
}

boolean done(){
for (int i = 0; i < H; ++i){
for (int j = 0; j < W; ++j){
if (F[i][j] != 0 && X[i][j] == 0) return false;
}
}
return true;
}

int h(){
int sum = 0;
for (int i = 0; i < H; ++i){
for (int j = 0; j < W; ++j){
if (F[i][j] != 0 && X[i][j] == 0) sum ++;
}
}
return sum / (max_W * max_W);
}

int idaStar(){
if (max_W == 0){
return 0;
}
for (limit = h(); limit < 100; ++limit){
if (dfs(0, 0)) return limit;
}
return -1;
}

boolean dfs(int s, int cost){
if (done()) return true;
if (s >= candicates.size()) return false;
if (cost + h() >= limit) return false;

for (int i = candicates.get(s)[0] + 1; i < H; i++){
for (int j = 0; j < W; ++j){
if (F[i][j] != 0 && X[i][j] == 0)
return false;
}
}

if (dfs(s + 1, cost)) return true;
int[][] x_backup = copy(X);
int pi = candicates.get(s)[0];
int pj = candicates.get(s)[1];
int w = T[pi][pj];
for (int l = 0; l < w; ++l){
for (int k = 0; k < w; ++k){
X[pi - l][pj - k]++;
}
}
if (dfs(s + 1, cost + 1)) return true;
X = copy(x_backup);
return false;
}

int[][] copy(int[][] X){
int n = X.length;
int m = X[0].length;
int[][] clone = new int[n][m];
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j){
clone[i][j] = X[i][j];
}
}
return clone;
}

void run() throws Exception {
is = oj ? System.in : new FileInputStream(new File(INPUT));
out = new PrintWriter(System.out);

long s = System.currentTimeMillis();
solve();
out.flush();
tr(System.currentTimeMillis() - s + "ms");
}

public static void main(String[] args) throws Exception {
new Main().run();
}

private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;

if (lenbuf == -1)
throw new InputMismatchException();
if (ptrbuf >= lenbuf) {
ptrbuf = 0;
try {
} catch (IOException e) {
throw new InputMismatchException();
}
if (lenbuf <= 0)
return -1;
}
return inbuf[ptrbuf++];
}

private boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126);
}

private int skip() {
int b;
while ((b = readByte()) != -1 && isSpaceChar(b))
;
return b;
}

private double nd() {
return Double.parseDouble(ns());
}

private char nc() {
return (char) skip();
}

private String ns() {
int b = skip();
StringBuilder sb = new StringBuilder();
while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
// ')
sb.appendCodePoint(b);
}
return sb.toString();
}

private char[] ns(int n) {
char[] buf = new char[n];
int b = skip(), p = 0;
while (p < n && !(isSpaceChar(b))) {
buf[p++] = (char) b;
}
return n == p ? buf : Arrays.copyOf(buf, p);
}

private char[][] nm(int n, int m) {
char[][] map = new char[n][];
for (int i = 0; i < n; i++)
map[i] = ns(m);
return map;
}

private int[] na(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = ni();
return a;
}

private int ni() {
int num = 0, b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
}

while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
}
}

private long nl() {
long num = 0;
int b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
}

while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
}
}

private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

private void tr(Object... o) {
if (!oj)
System.out.println(Arrays.deepToString(o));
}
}```

0 条评论

• 挑战程序竞赛系列（21）：3.2反转

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• 挑战程序竞赛系列（26）：3.5二分图匹配（1）

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• 挑战程序竞赛系列（28）：3.5最小费用流

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• LeetCode Contest 166

但是在用c++的快排的时候，被坑了，我一直的习惯是写自定义比较函数，没有写运算符重载，不知道为什么一直RE，浪费了挺多时间

• 3117 高精度乘法

3117 高精度练习之乘法  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解 题目描述 Description 给出...

• 浙大版《C语言程序设计（第3版）》题目集 习题5-4 使用函数求素数和

其中函数prime当用户传入参数p为素数时返回1，否则返回0；函数PrimeSum返回区间[m, n]内所有素数的和。题目保证用户传入的参数m≤n。

• 浙大版《C语言程序设计（第3版）》题目集 习题4-6 水仙花数

水仙花数是指一个N位正整数（N≥3），它的每个位上的数字的N次幂之和等于它本身。例如：153=13+53+33。 本题要求编写程序,计算所有N位水仙花数。

• 10:Challenge 3（树状数组直接修改）

总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 给一个长为N的数列，有M次操作，每次操作是以下两种之一： （1）...

• Day2上午解题报告

预计分数：100+0+60=160 实际分数：100+0+60=160 mmpT1数据错了。。。 T1遭遇 题目描述 你是能看到第一题的 friends呢。 —...

• P3808 【模版】AC自动机（简单版）

题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ，在保证正确的基础上只有两组数据，请不要恶意提交。 题目描述 给定n个模...