最后一个测试点TLE了,咋办
查看原帖
最后一个测试点TLE了,咋办
123538
Ff_c109楼主2021/5/29 15:52
#define int16 short int
#define int32 int
#define int48 long int
#define int64 long long int

#include <string>
#include <iostream>
#include <map>

using namespace std;

map <int48, map<int48, char> > a;
map <int48, map<int48, bool> > b;
int48 n;
int48 mx[] = {1, 1, 0, -1, -1, -1,  0,  1};
int48 my[] = {0, 1, 1,  1,  0, -1, -1, -1};
string demo = "yizhong";
int48 sum = 0;
map <int48, map<int48, bool> > flag;
//map <int48, map<int48, map<int48, map<int48, map<int48, bool> > > > > search_cache;

void search(int48 x, int48 y, int48 l, int48 mx, int48 my) {
    /*if (search_cache.find(x) != search_cache.end() &&
        search_cache[x].find(y) != search_cache.end() &&
        search_cache[x][y].find(l) != search_cache.end() &&
        search_cache[x][y][l].find(mx) != search_cache.end() &&
        search_cache[x][y][l][mx].find(my) != search_cache.end()) {
        if(search_cache[x][y][l][mx][my])
            return;
    }*/
	if(l == 6) {
		sum++;
		b[x][y] = true;
		for(int48 i = 1; i <= l; i++)
			b[x - (mx * i)][y - (my * i)] = true;
		return;
	}
	if(a[x][y] == demo[l]) {
			int48 xNew = x + mx,
				  yNew = y + my;
			if(xNew > n || yNew > n || xNew < 1 || yNew <1)
				return;
			if(!(flag.find(xNew) == flag.end()))
                if(!(flag[xNew].find(yNew) == flag[xNew].end()))
                    if(flag[xNew][yNew])
                        return;
			flag[xNew][yNew] = true;
			search(xNew, yNew, l + 1, mx, my);
			flag[xNew][yNew] = false;
	}else {
			int48 xNew = x + mx,
				  yNew = y + my;
			if(xNew > n || yNew > n || xNew < 1 || yNew <1)
				return;
			if(flag.find(xNew) != flag.end())
                if(flag[xNew].find(yNew) != flag[xNew].end())
                    if(flag[xNew][yNew])
                        return;
			flag[xNew][yNew] = true;
			search(xNew, yNew, l, mx, my);
			flag[xNew][yNew] = false;
	}
}
int32 main() {
	cin >> n;
	for(int48 i = 1; i <= n; i++)
		for(int48 j = 1; j <= n; j++) {
			cin >> a[i][j];
		}
	for(int48 i = 0; i < 8; i++) {
		for(int48 j = 1; j <= n; j++)
			for(int48 k = 1; k <= n; k++)
				search(j, k, 0, mx[i], my[i]);
	}
	//cout << sum << endl;
	for(int48 i = 1; i <= n; i++) {
		for(int48 j = 1; j <= n; j++) {
			/*if(b[i][j] == true)
				cout << a[i][j];*/
            bool temp = false;
            if(!(b.find(i) == b.end()))
                if(!(b[i].find(j) == b[i].end()))
                    if(b[i][j]) {
                        cout << a[i][j];
                        temp = true;
                    }
            if(!temp)
				cout << "*";
		}
		cout << endl;
	}
}
2021/5/29 15:52
加载中...