首页 > 其他分享 >Temp

Temp

时间:2023-11-15 19:47:10浏览次数:31  
标签:String Temp int start state toString new

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        StringBuilder start = new StringBuilder(), seq = new StringBuilder();
        while (sc.hasNext()) {
            String x = sc.next();
            start.append(x);
            if (!"x".equals(x)) seq.append(x);
        }

//        System.out.println(start);

        int t = 0;
        for (int i = 0; i < seq.length(); i ++ )
            for (int j = i + 1; j < seq.length(); j ++ )
                if (seq.charAt(i) > seq.charAt(j)) t ++ ;

        if (t % 2 == 1) System.out.println("unsolvable");
        else System.out.println(Astar(start.toString()));
    }

    static class PCS {
        char op;
        String state;
        public PCS(char op, String state) {
            this.op = op;
            this.state = state;
        }
    }

    static class PIS {
        int cnt;
        String state;
        public PIS(int cnt, String state) {
            this.cnt = cnt;
            this.state = state;
        }
    }

    public static int f(String state) {
        int res = 0;
        for (int i = 0; i < state.length(); i ++ )
            if (state.charAt(i) != 'x') {
                int t = state.charAt(i) - '1';
                res += Math.abs(i / 3 - t / 3) + Math.abs(i % 3 - t % 3);
            }

        return res;
    }

    public static String Astar(String start) {
        int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
        char[] op = {'u', 'r', 'd', 'l'};

        String end = "12345678x";
        Map<String, Integer> dist = new HashMap<>();
        Map<String, PCS> prev = new HashMap<>();
        PriorityQueue<PIS> heap = new PriorityQueue<>((a, b) -> a.cnt - b.cnt);

        heap.add(new PIS(f(start), start));
        dist.put(start, 0);

        while (!heap.isEmpty()) {
            PIS t = heap.poll();
            StringBuilder state = new StringBuilder(t.state);

            if (state.toString().equals(end)) break;

            int step = dist.getOrDefault(state.toString(), 0x3f3f3f3f);

            int x = 0, y = 0;
            for (int i = 0; i < state.length(); i ++ )
                if (state.charAt(i) == 'x') {
                    x = i / 3; y = i % 3;
                    break;
                }

            String source = state.toString();
            for (int i = 0; i < 4; i ++ ) {
                int a = x + dx[i], b = y + dy[i];
                if (a >= 0 && a < 3 && b >= 0 && b < 3) {
                    swap(state, x * 3 + y, a * 3 + b);
                    if (!dist.containsKey(state.toString()) || dist.get(state.toString()) > step + 1) {
                        dist.put(state.toString(), step + 1);
                        prev.put(state.toString(), new PCS(op[i], source));
                        heap.add(new PIS(dist.get(state.toString()) + f(state.toString()), state.toString()));
                    }
                    swap(state, x * 3 + y, a * 3 + b);
                }
            }
        }

        StringBuilder res = new StringBuilder();
        while (!end.equals(start)) {
            if (prev.containsKey(end)) {
                res.append(prev.get(end).op);
                end = prev.get(end).state;
            }
        }

        res.reverse();
        return res.toString();
    }

    public static void swap(StringBuilder s, int i, int j) {
        char t = s.charAt(i);
        s.setCharAt(i, s.charAt(j));
        s.setCharAt(j, t);
    }
}

标签:String,Temp,int,start,state,toString,new
From: https://www.cnblogs.com/llihaotian666/p/17834610.html

相关文章

  • template使用
    template语法template<typenameT>类/函数的实现注意:typename可以指定int,float等内置数据类型,自定义的class模板只有再使用的时候才会定义模板的定义不能与标准库冲突template用法重载的时候//打印不同的数据类型//print(5)//print(5.0f)//print("helloworld!")......
  • JDBC、数据库连接池、Spring JDBC:JdbcTemplate
    JDBCJDBC(JavaDataBaseConnectivity)概念:Java数据库连接,就是通过Java语言操作数据库。JDBC本质:其实是官方(sun公司)定义的一套操作所有关系型数据库的规则,即接口。各个数据库厂商去实现这套接口,提供数据库驱动jar包。我们可以使用这套接口(JDBC)编程,真正执行的代码是驱动jar包中的实......
  • template
    templatedemos(......
  • temp表空间满分析oracle
    1.查看当前temp使用率,尤其是执行计划是hashjoin,一定要关注tempselectdf.tablespace_name“Tablespace”,df.totalspace“Total(MB)”,nvl(FS.UsedSpace,0)“Used(MB)”,(df.totalspace-nvl(FS.UsedSpace,0))“Free(MB)”,round(100*(1-(nvl(fs.UsedSpace,......
  • SpringBoot: RestTemplate中文乱码
    1.问题原因RestTemplate的构造器创建了一个默认字符集为ISO-8859-1的StringHttpMessageConverter对象,它的默认编码格式为ISO-8859-1,所以需要修改这个StringHttpMessageConverter对象的编码格式即可2.解决方案@BeanpublicRestTemplategetRestTemplate(){......
  • vue2.0,把vform666、workFlow开源组件集成到vue-admin-template框架上心得体会
    以上三个都是vue2版本的开源项目,有的已经有vue3版本了,我把他们集成到一起,是出于练习的目的,也是消磨时间。vue-admin-template是一个很基础简洁的后台管理系统框架;vform666是可以用作表单低代码开发的组件项目;workFlow是模仿钉钉的工作流的组件项目,这三个项目在gitee上都能搜索到,......
  • 如何使用 RestTemplate 进行 Spring Boot 微服务通信示例
    概述下面我们将学习如何创建多个Springboot微服务以及如何使用RestTemplate类在多个微服务之间进行同步通信。微服务通信有两种风格:同步通讯异步通信同步通讯在同步通信的情况下,客户端发送请求并等待服务的响应。这里重要的一点是协议(HTTP/HTTPS)是同步的,客户端代码只......
  • 记录使用mongotemplete关于时间查询时的大坑
    1、问题:在使用条件查询mongdb数据库的时候,涉及到使用时间范围来查询数据,比如当时使用的是:1990-01-01T00:00:00到1900-02-02T00:00:00查询的是1月1号到1月2号两天的数据,但是在使用Query.query(criteria);进行查询的时候,和使用Aggregation.match(criteria);进行查询得出的结果不......
  • Recurrent Marked Temporal Point Processes: Embedding Event History to Vector
    目录概MotivationMarkedTemporalPointProcess代码DuN.,DaiH.,TrivediR.,UpadhyayU.,Gomez-RodriguzeM.andSongL.Recurrentmarkedtemporalpointprocesses:Embeddingeventhistorytovector.KDD,2016.概利用RNN学习强度函数\(\lambda^*\).在往下......
  • Temporal Point Processes
    目录TPPEvolutionarypointprocessesConditionalintensityfunction[\(t\)]Conditionalintensityfunction[\(t,\kappa\)]InferenceSimulationInverseMethodOgata’smodifiedthinningalgorithm例子RasmussenJ.G.Lecturenotes:Temporalpointprocessesandt......