题目描述

Alice和Bob在棋盘上玩游戏。

在一个n∗mn∗m的棋盘上有一颗棋子。为了方便起见，我们用(i,j)表示棋盘上从上到下第i行和从左到右第j列的位置。Alice和Bob约定了一个数字K，对于一个在(i,j)的棋子，他在不走到非法位置的情况下可以走向以下位置：

    (i+1,j)
    (i,j+1)
    (i+x,j+x) (1≤x≤k1≤x≤k)

走到非法位置的情况有：

    i>n
    j>m
    (i,j)是一个禁止通行的位置。

禁止通行的位置信息通过输入给出。

Alice和Bob在棋盘上按照该规则依次移动棋子，Alice先手,谁移动到(N,MN,M)处即获得胜利。有Q次询问，每次询问你假设棋子从某位置开始，并且在Alice和Bob足够聪明的情况下，Alice和Bob谁将获得游戏的胜利？
输入格式

第一行输入三个整数N,M,KN,M,K

其后N行，每行M个字符，如果第i行第j列字符是'.'，那么说明该位置可以通行，如果第i行第j列字符是'#'，那么说明该位置不能通行。保证该字符矩阵仅包含'.'和'#'。

接下来一行输入一个整数Q。 接下来Q行，每行两个整数x,yx,y，表示询问假设棋子从(x,y)开始，是先手获胜还是后手获胜。
输出格式

对于每次询问，输出一行。若先手获胜，输出"First"，否则输出"Second"。

code

//https://henanoi.com/p/17?tid=66f267fb2b043c91198c163e
#include <bits/stdc++.h>
using namespace std;
const int maxn = 330;
char mymap[maxn][maxn];// 时间复杂度 O(nmk)
int sg[maxn][maxn];
bool b[maxn][maxn];
int n,m,k;
int mex(long long x){//不属于这个集合的最小值
	long long t = x & (-x);// lowbit 最低位 1
	int cnt = 0;
	if(t == 0) return 0;//t == 0即为空集合 mex可以为0 
	if(t == 1) while(x & (1 << cnt)) cnt++;//倒着找 
	if(t > 1){
		while(t) t >>= 1,cnt++;//数t是第几位(1到n位) 也就是数0到n-1 往后一个数还要减1 
		cnt -= 2;	
	}
	return cnt;
}
int SG(int i,int j){
	if(i > n || j > m || mymap[i][j] == '#') return 0;
	if(i == n && j == m) return 0;
	if(b[i][j]) return sg[i][j];
	long long temp = 0;//sg函数一般不会太大 
	if(mymap[i+1][j] != '#' && i + 1 <= n && j <= m) temp = temp | (1 << SG(i+1,j));
	if(mymap[i][j+1] != '#' && i <= n && j + 1 <= m) temp = temp | (1 << SG(i,j+1));
	for(int c=1;c<=k;c++) if(i + c <= n && j + c <= m) if(mymap[i+c][j+c] != '#') temp = temp | (1 << SG(i+c,j+c));
	b[i][j] = 1;
	return sg[i][j] = mex(temp);
}
int main(){
//	for(int i=0;i<=10;i++) cout<<i<<' '<<mex(i)<<endl;
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mymap[i][j];
		}
	}
	sg[n][m] = 0;
	int t,tx,ty;
	cin>>t;
	while(t--){
		cin>>tx>>ty;
		if(SG(tx,ty) == 0) cout<<"Second"<<endl;
		//注意这里是 SG(tx,ty) == 0 而不是 sg[i][j] == 0,因为前面可能不会遍历到后面的 
		else cout<<"First"<<endl;
	}
	return 0;
}

怎样使它的时间复杂度更小？ Time Exceeded

样例数据

input

2 2 0
.#
..
2
1 1
2 1

output

Second
First

input

2 2 1
..
..
1
1 1

output

First

input

3 4 0
....
.#..
....
1
3 2

output

Second

数据规模与约定

对于所有数据：

    2≤N≤300 2≤N≤300
    K≥0 K≤N−1
    保证(N,M)处可以通行
    保证从任意位置开始都将棋子移动到(N,M)
    1≤Q≤300 对于1≤i≤Q1,保证1≤xi≤N,1≤yi≤M