1995 三子棋

题目来源: syu校赛
基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题

小的时候大家一定玩过“井”字棋吧。也就是在九宫格中,只要任意行、列,或者任意连续对角线上面出现三个相同的,就能获胜。现在小明和小花也在玩三子棋,但是他们不是在九宫格里,而是在3×4的格子里面。现在小明先下,但是他知道小花这个人很聪明,他想知道第一步下在哪一个地方最合适,你能帮帮他吗?

Input

第一行输入一个整数T,表示数据组数(1<T<10000);
第二行输入两个整数x,y,表示3×4格子里面的一个坐标(x,y)(1<=x<=3,1<=y<=4);

Output

每组数据输出最后小明输赢的结果,如果小明一定能赢,第一行输出“Win”,第二行输出小明所需要花的最少步数;如果小明跟小花只能打成平手,第一行输出“Equal”,第二行输出数字0;如果小明不能赢也不能跟小花打成平手,第一行输出“Lose”,第二行输出小花赢小明所需要花的最少步数


题解:

抱着作a+b的心态开始刷基础题,结果基础题怎么这么不水呢么。。
没想到啥好方法,就自己跟自己下模拟;
策略就和一般五子棋差不多,关于最少步数,由于对手也是绝顶聪明的,所以不会让你下在很快赢的地方,其实应该算最多步数的最少步数那个意思。。大概;

棋盘是对称的,所以只要看(1,1)(1,2)(2,1)(2,2)四个点就可以;
如下表:

1 2 2 1
3 4 4 3
1 2 2 1

然后结论是对先手来说(1,1)(1,2)(2,2)必胜,(2,1)平局;

(1,1)的最短路是6:
先手:11->12->31->23->32形成“双二”再下一步就赢了
后手:21->13->21->34->

(1,2)的最短路是4:
先手:12->23->32形成“双二”再下一步就赢了
后手:13->34->

(2,2)的最短路是4:
先手:22->13->11形成“双二”再下一步就赢了
后手:23->31->

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <cmath>
#include <list>
using namespace std;

int a[3][4]={6,4,4,6,0,4,4,0,6,4,4,6};
int main(){
int t,x,y;
scanf("%d",&t);
while(t--){
scanf("%d%d",&x,&y);
x--;
y--;
if(a[x][y]==0)printf("Equal\n0\n");
else printf("Win\n%d\n",a[x][y]);
}
return 0;
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2018-2021 LeFlacon

奶茶一杯 快乐起飞

支付宝
微信