LeeCode 1728 任意图上博弈

2024-05-01 05:04
文章标签 博弈 意图 leecode 1728

本文主要是介绍LeeCode 1728 任意图上博弈,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意

传送门 LeeCode 1728 猫和老鼠 II

题解

任意图上博弈,可参考 Games on arbitrary graphs。具体而言,将博弈双方位置加之先后手状态看作任意图上的一个节点,并根据状态转移建立反图。对于可以确定胜负态的节点,以其为起点,使用类似拓扑序更新的操作不断递推其余节点的状态。对于 n × m n\times m n×m的方格,任意图博弈求解时间复杂度为 O ( ( n m ) 2 max ⁡ ( n , m ) ) O\Big((nm)^{2}\max(n,m)\Big) O((nm)2max(n,m))

#include <bits/stdc++.h>
using namespace std;class Solution {public:bool canMouseWin(vector<string>& grid, int catJump, int mouseJump) {int n = grid.size(), m = grid[0].size();int mx = -1, my = -1;int cx = -1, cy = -1;int fx = -1, fy = -1;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {auto c = grid[i][j];if (c == 'M') {mx = i, my = j;}if (c == 'C') {cx = i, cy = j;}if (c == 'F') {fx = i, fy = j;}}}const vector<int> dx = {0, 0, -1, 1};const vector<int> dy = {-1, 1, 0, 0};int pos_num = n * m;int state_num = pos_num * pos_num * 2;vector<vector<int>> g(state_num);auto get = [&](int u, int v, int who) {return u + v * pos_num + who * pos_num * pos_num;};auto judge = [&](int x, int y) {return 0 <= x && x < n && 0 <= y && y < m && grid[x][y] != '#';};auto ed = [&](int cv, int mv) {int fv = fx * m + fy;return cv == mv || cv == fv || mv == fv;};for (int cv = 0; cv < pos_num; ++cv) {for (int mv = 0; mv < pos_num; ++mv) {if (ed(cv, mv)) {continue;}for (int who = 0; who < 2; ++who) {int w = who == 0 ? cv : mv;int sx = w / m, sy = w % m;int lim = who == 0 ? catJump : mouseJump;for (int k = 0; k < (int)dx.size(); ++k) {int x = sx, y = sy;for (int d = 0; d <= lim; ++d) {if (!judge(x, y)) {break;}if (who == 0) {g[get(x * m + y, mv, who ^ 1)].push_back(get(cv, mv, who));} else {g[get(cv, x * m + y, who ^ 1)].push_back(get(cv, mv, who));}x += dx[k];y += dy[k];}}}}}vector<int> indeg(state_num);for (int u = 0; u < state_num; ++u) {for (int v : g[u]) {indeg[v] += 1;}}vector<int> win(state_num, -1);function<void(int)> dfs = [&](int v) {for (int u : g[v]) {if (win[u] == -1) {if (win[v] == 0) {win[u] = 1;} else {indeg[u] -= 1;if (indeg[u] == 0) {win[u] = 0;}}if (win[u] != -1) {dfs(u);}}}};for (int cv = 0; cv < pos_num; ++cv) {int x = cv / m, y = cv % m;if (judge(x, y)) {for (int who = 0; who < 2; ++who) {int v = get(cv, cv, who);win[v] = who ^ 1;dfs(v);}}}for (int v = 0; v < pos_num; ++v) {int x = v / m, y = v % m;int f = fx * m + fy;if (judge(x, y) && v != f) {int u = get(f, v, 1);win[u] = 0;dfs(u);int w = get(v, f, 0);win[w] = 0;dfs(w);}}int res = win[get(cx * m + cy, mx * m + my, 1)];return res == 1;}
};

这篇关于LeeCode 1728 任意图上博弈的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/950776

相关文章

poj2505(典型博弈)

题意:n = 1,输入一个k,每一次n可以乘以[2,9]中的任何一个数字,两个玩家轮流操作,谁先使得n >= k就胜出 这道题目感觉还不错,自己做了好久都没做出来,然后看了解题才理解的。 解题思路:能进入必败态的状态时必胜态,只能到达胜态的状态为必败态,当n >= K是必败态,[ceil(k/9.0),k-1]是必胜态, [ceil(ceil(k/9.0)/2.0),ceil(k/9.

hdu3389(阶梯博弈变形)

题意:有n个盒子,编号1----n,每个盒子内有一些小球(可以为空),选择一个盒子A,将A中的若干个球移到B中,满足条件B  < A;(A+B)%2=1;(A+B)%3=0 这是阶梯博弈的变形。 先介绍下阶梯博弈: 在一个阶梯有若干层,每层上放着一些小球,两名选手轮流选择一层上的若干(不能为0)小球从上往下移动,最后一次移动的胜出(最终状态小球都在地面上) 如上图所示,小球数目依次为

AI模型的未来之路:全能与专精的博弈与共生

人工智能(AI)领域正迅速发展,伴随着技术的不断进步,AI模型的应用范围也在不断扩展。当前,AI模型的设计和使用面临两个主要趋势:全能型模型和专精型模型。这两者之间的博弈与共生将塑造未来的AI技术格局。本文将从以下七个方面探讨AI模型的未来之路,并提供实用的代码示例,以助于研究人员和从业者更好地理解和应用这些技术。 一、AI模型的全面评估与比较 1.1 全能型模型 全能型AI模型旨在在多

简单取石子游戏~博弈

很坑爹的小游戏,至于怎么坑爹,嘎嘎~自己研究去吧~! #include<stdio.h>#include<windows.h>#include<iostream>#include<string.h>#include<time.h>using namespace std;void Loc(int x,int y);/*定位光标*/void Welcome(); /*创建欢迎界面*/

综合评价 | 基于熵权-变异系数-博弈组合法的综合评价模型(Matlab)

目录 效果一览基本介绍程序设计参考资料 效果一览 基本介绍 根据信息熵的定义,对于某项指标,可以用熵值来判断某个指标的离散程度,其信息熵值越小,指标的离散程度越大, 该指标对综合评价的影响(即权重)就越大,如果某项指标的值全部相等,则该指标在综合评价中不起作用。因此,可利用信息熵这个工具,计算出各个指标的权重,为多指标综合评价提供依据。 变异系数只在平均值不为

“苹果税”引发的苹果与腾讯、字节跳动之间的纷争与博弈

北京时间9月10日凌晨一点的Apple特别活动日渐临近,苹果这次将会带来iPhone16系列新品手机及其他硬件产品的更新,包括iPad、Apple Watch、AirPods等。从特别活动的宣传图和宣传标语“閃亮時刻”来看,Apple Intelligence将会是史上首次推出,无疑将会是iOS 18的重头戏和高光时刻。 不过就在9月2日,一则“微信可能不支持iPhone16”的

美业收银系统怎么选择?博弈美业系统展示、美业SaaS管理系统源码戳

美业收银系统是一种专为美容、美发、美甲、SPA等美业门店设计的全面性结账解决方案,其重要性在于它为门店提供了全面的业务管理功能。美业收系统可以处理销售、预约管理、库存追踪和员工绩效等多项任务,不仅能够简化交易流程,还能提高门店管理效率,是提升门店竞争力和盈利能力的利器。 一套优秀的美业收银系统要专业、智能、高效、便捷!博弈美业包括PC、pad、手机APP、小程序四大端口,一套系统解决连锁美业多种

智能对决:提示词攻防中的AI安全博弈

智能对决:提示词攻防中的AI安全博弈 在2024年上海AIGC开发者大会上,知名提示词爱好者工程师云中嘉树发表了关于AI提示词攻防与安全博弈的精彩演讲。他深入探讨了当前AI产品的安全现状,提示词攻击的常见手段及其应对策略。本文将对他的演讲进行详细的解读与分析,并结合实际案例和技术手段,探讨如何在AI应用开发中提高安全性。 1. AI产品安全现状 随着大模型(如GPT系列)和AI应用的普及,A

LeeCode 30

LeeCode 30 题目: 思路: 朴素的想法,是创建一个 m p mp mp哈希表记录 w o r d s words words中所有字符出现的次数,令 n n n为 s . s i z e ( ) s.size() s.size(), m m m为 w o r d s . s i z e ( ) words.size() words.size(), l e n len len为

综合评价 | 基于层次-熵权-博弈组合法的综合评价模型(Matlab)

目录 效果一览基本介绍程序设计参考资料 效果一览 基本介绍 AHP层次分析法是一种解决多目标复杂问题的定性和定量相结合进行计算决策权重的研究方法。该方法将定量分析与定性分析结合起来,用决策者的经验判断各衡量目标之间能否实现的标准之间的相对重要程度,并合理地给出每个决策方案的每个标准的权数,利用权数求出各方案的优劣次序,比较有效地应用于那些难以用定量方法解决的课题