洛谷 P1379 八數位難題 A* 題解

来源:https://www.cnblogs.com/cppom/p/-/P1379-tijie
-Advertisement-
Play Games

剛做完一道模板A*,看到這題我直接小腦萎縮了... 阿米諾斯!這怎麼用A*?!——剛開題的我 beeeeeeeeee like 甚至比模板簡單(這是綠的...) 其實會是會但是紙張的是這玩意我不會搞估價函數我草! 然後突然想到能不能把這個狀態下有多少個數字不在目標位置作為估價函數? 我喜歡 \(ID ...


剛做完一道模板A*,看到這題我直接小腦萎縮了...

阿米諾斯!這怎麼用A*?!——剛開題的我 beeeeeeeeee like

甚至比模板簡單(這是綠的...)

其實會是會但是紙張的是這玩意我不會搞估價函數我草!

然後突然想到能不能把這個狀態下有多少個數字不在目標位置作為估價函數?

我喜歡 \(IDA*\),有興趣的讀者可以寫普通的 \(A*\)

畢竟 \(IDA*\) 好寫啊。

結果調了很久,wssb。

本題代碼
#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
	i128 f=1;
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}
void writing(i128 x)
{
	if(x>=10)writing(x/10);
	putchar(x%10+'0');
}
void write(i128 x)
{
	if(x<0)
	{
		cout<<'-';
		x=-x;
	}
	writing(x);
}
char ch[20];
LL en[4][4]=
{
    {0,0,0,0},
    {0,1,2,3},
    {0,8,0,4},
    {0,7,6,5}
};
LL a[10][10],sd;
bool don;
LL dx[]={0,1,-1,0};
LL dy[]={1,0,0,-1};
bool che()
{
	rep(i,1,3,1)
	{
		rep(j,1,3,1)
		{
			if(en[i][j]!=a[i][j])return 0;
		}
	}
	return 1;
}
bool gg(LL sp)
{
	LL sum=0;
	rep(i,1,3,1)
	{
		rep(j,1,3,1)
		{
			if(en[i][j]!=a[i][j])
			{
				sum++;
				if(sum+sp>sd)
				{
					return 0;
				}
			}
		}
	}
	return 1;
}
void idastar(LL sp,LL x,LL y,LL bef)
{
	if(sp==sd)
	{
		if(che())don=1;
		return;
	}
	repn(i,0,4,1)
	{
		LL nx=x+dx[i],ny=y+dy[i];
		if(nx<1||nx>3||ny<1||ny>3||bef+i==3)continue;
		swap(a[x][y],a[nx][ny]);
		if(gg(sp)&&!don)
		{
			idastar(sp+1,nx,ny,i);
		}
		swap(a[x][y],a[nx][ny]);
	}
}
int main()
{
	LL x,y;
	cin>>ch;
	repn(i,0,9,1)
    {
        a[i/3+1][i%3+1]=ch[i]-'0';
        if(ch[i]-'0'==0)
        {
        	x=i/3+1;
			y=i%3+1;
		}
    }
    if(che())
    {
    	cout<<0<<endl;
	}
	else
	{
		while(1)
		{
			sd++;
			idastar(0,x,y,-1);
			if(don)
			{
				cout<<sd<<endl;
				break;
			}
		}
	}
	return 0;
}

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 所有主要的瀏覽器都內置了一個XML解析器,用於訪問和操作XML XML 解析器 在訪問XML文檔之前,必須將其載入到XML DOM對象中 所有現代瀏覽器都有一個內置的XML解析器,可以將文本轉換為XML DOM對象 解析文本字元串 以下示例將一個文本字元串解析為XML DOM對象,並使用JavaSc ...
  • 概述:C++結構體的`sizeof`不總是等於每個成員的`sizeof`之和,因為對齊和填充影響了記憶體佈局。未對齊的結構體可能存在間隙,而對齊的結構體會插入填充以保持對齊。通過示例展示了結構體的記憶體對齊和填充,以及如何使用模板元編程列印結構體成員的偏移量,深入理解記憶體佈局。 在C++中,結構體的si ...
  • C++ 語法 讓我們將以下代碼分解以更好地理解它: 示例 #include <iostream> using namespace std; int main() { cout << "Hello World!"; return 0; } 示例解釋 第 1 行:#include <iostream> ...
  • https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-interview-150 對於一個可以構成“碗”的序列,最後裝滿水的話應該和最短的一邊齊平,那麼可以左右各遍歷 ...
  • 1 Spark 的 local 模式 Spark 運行模式之一,用於在本地機器上單機模擬分散式計算的環境。在 local 模式下,Spark 會使用單個 JVM 進程來模擬分散式集群行為,所有 Spark 組件(如 SparkContext、Executor 等)都運行在同一個 JVM 進程中,不涉 ...
  • 雲原生技術正重塑IT領域,本文深度剖析了其發展歷程、核心概念、生態系統及實踐案例,展望未來趨勢,揭示了這一技術如何引領企業轉型與創新。 關註【TechLeadCloud】,分享互聯網架構、雲服務技術的全維度知識。作者擁有10+年互聯網服務架構、AI產品研發經驗、團隊管理經驗,同濟本復旦碩,復旦機器人 ...
  • Qt 是一個跨平臺C++圖形界面開發庫,利用Qt可以快速開發跨平臺窗體應用程式,在Qt中我們可以通過拖拽的方式將不同組件放到指定的位置,實現圖形化開發極大的方便了開發效率,本章將重點介紹如何運用`QProcess`組件實現針對進程的控制管理等。當你在使用Qt進行跨平臺應用程式開發時,經常需要與外部進... ...
  • 對於程式員來說這個單詞完全擁有另外一個含義,Spring指的是一個開源項目,而這個項目非常厲害。而Spring與JSR、JarkataEE淵源頗深。 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...