博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【codevs1949】兔兔与蛋蛋的游戏
阅读量:5111 次
发布时间:2019-06-13

本文共 4431 字,大约阅读时间需要 14 分钟。

没什么好解释的,博弈论神题,代码都能看懂

var        m,n,sx,sy,sum:longint;        map:array[0..40,0..40] of char;        id:array[0..40,0..40] of longint;        win,del,v:array[0..2010] of boolean;        g:array[0..2000,0..2000] of longint;        link:array[0..2001] of longint;        procedure get_inf;        var i,j:longint;        begin                readln(n,m);                for i:=1 to n do                begin                        for j:=1 to m do                        begin                                read(map[i][j]);                                if map[i][j]='.' then                                begin                                        sx:=i;sy:=j;                                        sum:=1;id[i][j]:=1;                                end;                        end;                        readln;                end;                for i:=1 to n do                for j:=1 to m do                if (map[i][j]='X') and ((i+j) and 1=(sx+sy) and 1) or (map[i][j]='O') and ((i+j) and 1 <> (sx+sy) and 1) then                begin                        inc(sum);                        id[i][j]:=sum;                end;                for i:=1 to n do                for j:=1 to m do                if id[i][j]>0 then                begin                        if id[i-1][j]>0 then                        begin                                inc(g[id[i][j],0]);                                g[id[i][j],g[id[i][j],0]]:=id[i-1][j];                                inc(g[id[i-1][j],0]);                                g[id[i-1][j],g[id[i-1][j],0]]:=id[i][j];                        end;                        if id[i][j-1]>0 then                        begin                                inc(g[id[i,j],0]); g[id[i,j],g[id[i,j],0]]:=id[i,j-1];                                inc(g[id[i,j-1],0]); g[id[i,j-1],g[id[i,j-1],0]]:=id[i,j];                        end;                end;        end;        function find(x:longint):boolean;        var i,y:longint;        begin                v[x]:=true;                for y:=1 to g[x][0] do                begin                        i:=g[x][y];                        if not v[i] and not del[i] then                        begin                                v[i]:=true;                                if (link[i]=0) or find(link[i]) then                                begin                                        link[i]:=x;link[x]:=i;                                        exit(true);                                end;                        end;                end;                exit(false);        end;        function check:boolean;        var t:longint; can:boolean;        begin                if link[id[sx,sy]]=0 then exit(false);                del[id[sx,sy]]:=true; t:=link[id[sx,sy]];                link[t]:=0; link[id[sx,sy]]:=0;                fillchar(v,sizeof(v),0);                can:=find(t);                if not can then                begin                link[t]:=id[sx,sy];                link[id[sx,sy]]:=t;                end;                del[id[sx,sy]]:=false;                exit(not can);        end;        procedure main;        var                i,q,tot,x,y,t:longint;        begin                for i:=1 to sum do                if link[i]=0 then                begin                        fillchar(v,sizeof(v),0);                        find(i);                end;                read(q); tot:=0;                for i:=1 to q do                begin                        win[i]:=check;                        read(x,y);                        del[id[sx,sy]]:=true;                        t:=link[id[sx,sy]];                        link[t]:=0; link[id[sx,sy]]:=0;                        fillchar(v,sizeof(v),0);                        find(t);                        sx:=x; sy:=y;                        if win[i] and check then inc(tot) else win[i]:=false;                        read(x,y);                        del[id[sx,sy]]:=true;                        t:=link[id[sx,sy]];                        link[t]:=0; link[id[sx,sy]]:=0;                        fillchar(v,sizeof(v),0);                        find(t);                        sx:=x; sy:=y;                end;                writeln(tot);                for i:=1 to q do                if win[i] then writeln(i);        end;        begin                get_inf;                main;        end.

 

转载于:https://www.cnblogs.com/victorslave/p/4797618.html

你可能感兴趣的文章
事物随笔
查看>>
kmp 字符串匹配
查看>>
vim输出高亮代码到office
查看>>
在VMWare上安装Arch Linux
查看>>
[arc076F]Exhausted? 贪心+堆
查看>>
MYSQL用户操作管理大杂烩
查看>>
stdafx.h有什么用
查看>>
神经网络与深度学习(1):神经元和神经网络
查看>>
Python-事件驱动模型代码
查看>>
Linux-NFS原理介绍
查看>>
maven工程仿springboot手写代码区分开发测试生产
查看>>
javascript高级编程笔记01(基本概念)
查看>>
unicode 字符范围
查看>>
确保对象在被使用前的初始化
查看>>
理解[].forEach.call()
查看>>
sdcms IIS7 windows server 2008 配置后,无法修改模板页面
查看>>
【整理】HTML5游戏开发学习笔记(4)- 记忆力游戏
查看>>
学习资料 数据结构
查看>>
python 标准库中队列相关模块介绍(子博客)
查看>>
excel中的数据整列填充
查看>>