关于图灵杯题目

常规
1

为什么我的鱼棋一分拿不到QAQ，样例和附加样例都过的，怎么就被hack完了QAQ

#include<bits/stdc++.h>
#define mk make_pair
using namespace std;
const int maxn = 205;
const int Kw[] = {0,1,-1},Bw[] = {1,-1};
const int Nwx[] = {1,1,-1,-1,2,-2,2,-2};
const int Nwy[] = {2,-2,2,-2,1,1,-1,-1};
const int Rwx[] = {0,0,1,-1},Rwy[] = {1,-1,0,0};
int T,n,m,sx,sy,ans; char sta,x;
vector<vector<char> > mp; map<int,map<int,int> > vis;
queue<pair<pair<pair<int,int>,char>,pair<int,int> > > q;
// void change(int x,int y,int st,int tot,char nxt) { q.push(mk(mk(mk(st,tot + 1),nxt),mk(x,y))); }
void move(int x,int y,int st,int tot,char now) { q.push(mk(mk(mk(st,tot),now),mk(x,y))); }
void bfs() { // 恶心死了这题
    while (!q.empty()) q.pop();
    for (int i = 1;i <= n;i ++)
        for (int j = 1;j <= m;j ++)
            vis[i][j] = -1;
    q.push(mk(mk(mk(0,0),sta),mk(sx,sy))); ans = 1e9;
    while (!q.empty()) {
        auto top = q.front(); q.pop();
        int x = top.second.first, y = top.second.second, st = top.first.first.first,tot = top.first.first.second;
        char now = top.first.second;
        if (x < 1 || x > n || y < 0 || y > m || (vis[x][y] != -1 && vis[x][y] != st) || mp[x][y] == '#') continue;
        // change & move
        vis[x][y] = st; if (mp[x][y] == 'T') { ans = min(ans,st + tot); }
        if (st + tot >= ans) continue;
        for (int i = 0;i < 3;i ++) 
            for (int j = 0;j < 3;j ++)
                if (i != 0 && j != 0)
                    move(x + Kw[i],y + Kw[j],st + 1,tot + (now != 'K'),'K');
        for (int i = 0;i < 2;i ++)
            for (int j = 0, nx = x + Bw[i], ny = y + Bw[j];j < 2;j ++, nx = x + Bw[i], ny = y + Bw[j]) 
                while (nx > 0 && nx <= n && ny > 0 && ny <= m && mp[nx][ny] != '#') {
                    move(nx,ny,st + 1,tot + (now != 'B'),'B');
                    nx += Bw[i], ny += Bw[j];
                }
        for (int i = 0;i < 8;i ++) move(x + Nwx[i],y + Nwy[i],st + 1,tot + (now != 'N'),'N');
        for (int i = 0,nx = x + Rwx[i],ny = y + Rwy[i];i < 4;i ++,nx = x + Rwx[i], ny = y + Rwy[i]) 
            while (nx > 0 && nx <= n && ny > 0 && ny <= m && mp[nx][ny] != '#') {
                move(nx,ny,st + 1,tot + (now != 'R'),'R');
                nx += Rwx[i], ny += Rwy[i];
            }
    }
    if (ans == 1e9) ans = -1;
}
int main() {
    scanf("%d",&T);
    while (T --) {
        scanf("%d%d %c",&n,&m,&sta);
        getchar();
        mp.clear(); mp.push_back({});
        for (int i = 1;i <= n;i ++) {
            mp.push_back({}); mp[i].push_back('#');
            for (int j = 1;j <= m;j ++) { 
                x = getchar();
                mp[i].push_back(x);
                if (x == 'S') sx = i, sy = j;
            }
            getchar();
        }
        bfs(); printf("%d\n",ans);
    }
    return 0;
}

真的蚌埠住了

3 个赞
2

你的好短啊，我的250行 :rofl:

3 个赞
3

借一下楼，有没有大佬能不能也帮我也看看啊

3 个赞
4 
#include <bits/stdc++.h>
using namespace std;

int T, n, m;
char c;

struct node {
	int x, y, step;
	char kind;
};

int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {0, -1}, {1, -1}, {1, 0}, {1, -1}};

int dir2[8][2] = {{-1, -2}, {-2, -1}, {1, -2}, {2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}};

bool in(int x, int y) {
	return x > 0 && x <= n && y > 0 && y <= m;
}

int chan(char c) {
	if(c == 'K') {
		return 1;
	}
	if(c == 'N') {
		return 2;
	}
	if(c == 'R') {
		return 3;
	}
	return 4;
}

int main() {

	scanf("%d", &T);

	while(T--) {
		scanf("%d%d", &n, &m);
		cin >> c;
		char mp[n + 5][m + 5];
		int sx, sy, ex, ey;

		bool flag = false, vis[n + 5][m + 5] = {0}, vv[n + 5][m + 5][5] = {0};

		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= m; j++) {
				cin >> mp[i][j];
				if(mp[i][j] == 'S') sx = i, sy = j;
				if(mp[i][j] == 'T') ex = i, ey = j;
			}
		}
		queue<node> q;
		q.push({sx, sy, 0, c});
		while(!q.empty()) {
			node k = q.front();
			q.pop();
			if(k.x == ex && k.y == ey) {
				flag = 1;
				printf("%d\n", k.step);
				break;
			}
			if(k.kind == 'K') {
				for(int i = 0; i < 8; i++) {
					node ans = k;
					ans.x += dir[i][0], ans.y += dir[i][1];
					if(mp[ans.x][ans.y] != '#' && in(ans.x, ans.y) && !vis[ans.x][ans.y]) {
						ans.step = k.step + 1;
						vis[ans.x][ans.y] = 1;
						q.push(ans);
					}
				}
				node ans = k;
				ans.step = k.step + 1;
				if(!vv[k.x][k.y][2]) {
					ans.kind = 'N';
					vv[k.x][k.y][2] = 1;
					q.push(ans);
				}
				if(!vv[k.x][k.y][3]) {
					ans.kind = 'R';
					vv[k.x][k.y][3] = 1;
					q.push(ans);
				}
				if(!vv[k.x][k.y][4]) {
					ans.kind = 'B';
					vv[k.x][k.y][4] = 1;
					q.push(ans);
				}
			}
			if(k.kind == 'N') {
				for(int i = 0; i < 8; i++) {
					node ans = k;
					ans.x += dir2[i][0], ans.y += dir2[i][1];
					if(mp[ans.x][ans.y] != '#' && in(ans.x, ans.y) && !vis[ans.x][ans.y]) {
						ans.step = k.step + 1;
						vis[ans.x][ans.y] = 1;
						q.push(ans);
					}
				}
				node ans = k;
				ans.step = k.step + 1;
				if(!vv[k.x][k.y][1]) {
					ans.kind = 'K';
					vv[k.x][k.y][1] = 1;
					q.push(ans);
				}
				if(!vv[k.x][k.y][3]) {
					ans.kind = 'R';
					vv[k.x][k.y][3] = 1;
					q.push(ans);
				}
				if(!vv[k.x][k.y][4]) {
					ans.kind = 'B';
					vv[k.x][k.y][4] = 1;
					q.push(ans);
				}
			}
			if(k.kind == 'R') {
				for(int i = k.x - 1; i > 0; i--) {
					if(mp[i][k.y] == '#') {
						break;
					}
					node ans = k;
					ans.x = i, ans.step = k.step + 1;
					if(!vis[ans.x][ans.y]) {
						vis[ans.x][ans.y] = 1;
						q.push(ans);
					}
				}
				for(int i = k.x + 1; i <= n; i++) {
					if(mp[i][k.y] == '#') {
						break;
					}
					node ans = k;
					ans.x = i, ans.step = k.step + 1;
					if(!vis[ans.x][ans.y]) {
						vis[ans.x][ans.y] = 1;
						q.push(ans);
					}
				}
				for(int i = k.y - 1; i > 0; i--) {
					if(mp[k.x][i] == '#') {
						break;
					}
					node ans = k;
					ans.y = i, ans.step = k.step + 1;
					if(!vis[ans.x][ans.y]) {
						vis[ans.x][ans.y] = 1;
						q.push(ans);
					}
				}
				for(int i = k.y + 1; i <= m; i++) {
					if(mp[k.x][i] == '#') {
						break;
					}
					node ans = k;
					ans.y = i, ans.step = k.step + 1;
					if(!vis[ans.x][ans.y]) {
						vis[ans.x][ans.y] = 1;
						q.push(ans);
					}
				}
				node ans = k;
				ans.step = k.step + 1;
				if(!vv[k.x][k.y][1]) {
					ans.kind = 'K';
					vv[k.x][k.y][1] = 1;
					q.push(ans);
				}
				if(!vv[k.x][k.y][2]) {
					ans.kind = 'N';
					vv[k.x][k.y][2] = 1;
					q.push(ans);
				}
				if(!vv[k.x][k.y][4]) {
					ans.kind = 'B';
					vv[k.x][k.y][4] = 1;
					q.push(ans);
				}
			}
			if(k.kind == 'B') {
				for(int i = 1; i < min(k.x, k.y); i++) {
					if(mp[k.x - i][k.y - i] == '#') {
						break;
					}
					node ans = k;
					ans.x = k.x - i, ans.y = k.y - i, ans.step = k.step + 1;
					if(!vis[ans.x][ans.y]) {
						vis[ans.x][ans.y] = 1;
						q.push(ans);
					}
				}
				for(int i = 1; i <= min(n - k.x, m - k.y); i++) {
					if(mp[k.x + i][k.y + i] == '#') {
						break;
					}
					node ans = k;
					ans.x = k.x + i, ans.y = k.y + i, ans.step = k.step + 1;
					if(!vis[ans.x][ans.y]) {
						vis[ans.x][ans.y] = 1;
						q.push(ans);
					}
				}
				for(int i = 1; i <= min(k.x - 1, m - k.y); i++) {
					if(mp[k.x - i][k.y + i] == '#') {
						break;
					}
					node ans = k;
					ans.x = k.x - i, ans.y = k.y + i, ans.step = k.step + 1;
					if(!vis[ans.x][ans.y]) {
						vis[ans.x][ans.y] = 1;
						q.push(ans);
					}
				}
				for(int i = 1; i <= min(n - k.x, k.y - 1); i++) {
					if(mp[k.x + i][k.y - i] == '#') {
						break;
					}
					node ans = k;
					ans.x = k.x + i, ans.y = k.y - i, ans.step = k.step + 1;
					if(!vis[ans.x][ans.y]) {
						vis[ans.x][ans.y] = 1;
						q.push(ans);
					}
				}
				node ans = k;
				ans.step = k.step + 1;
				if(!vv[k.x][k.y][1]) {
					ans.kind = 'K';
					vv[k.x][k.y][1] = 1;
					q.push(ans);
				}
				if(!vv[k.x][k.y][2]) {
					ans.kind = 'N';
					vv[k.x][k.y][2] = 1;
					q.push(ans);
				}
				if(!vv[k.x][k.y][3]) {
					ans.kind = 'R';
					vv[k.x][k.y][3] = 1;
					q.push(ans);
				}
			}
		}
		if(!flag) {
			printf("-1\n");
		}
	}
	return 0;
}
3 个赞