球调代码 WA on 11,12,15
查看原帖
球调代码 WA on 11,12,15
871641
封禁用户楼主2023/8/22 10:35
#include<bits/stdc++.h>
using namespace std;
const int inf = 355;
const int Max = 0x7fffffff;
#define pii pair<int,int>
#define fi first
#define se second
#define mp(a,b) make_pair(a,b)
int army[inf][inf]; 

int dif[inf][inf];
struct node {
	int x,y;
	int step;
	int t1;//ys times
	int t2;//sy times
};
int tx,ty;
int n,m,d;
int c1,c2;
queue<node> q;
int dx[8] = {-1,0,0,1,-1,-1,1,1};
int dy[8] = {0,-1,1,0,-1,1,-1,1};
int vis[inf][inf][16][16];
int lk[inf][inf];
node ans = (node) {0,0,Max,Max,Max};

bool check(node a,node b) {
	if(a.step != b.step) {
		return a.step < b.step;
	}
	if(a.t1 + a.t2 != b.t1 + b.t2) {
		return a.t1 + a.t2 < b.t1 + b.t2;
	}
	return a.t1 < b.t1;
}

void bfs() {
	while(!q.empty()) {
		node x = q.front();
		if(x.step > ans.step) {
			q.pop();
			continue;
		}
		for(int i = 0;i<8;i++) {
			int nx = x.x + dx[i];
			int ny = x.y + dy[i];
			if(nx < 1 || ny < 1 || nx > n || ny > m || army[nx][ny]) {
				continue;
			}
			if(lk[nx][ny]) {//yinshen
				if(x.t1 >= c1 || vis[nx][ny][x.t1+1][x.t2]) {
					continue;
				}
				vis[nx][ny][x.t1+1][x.t2] = 1;
				q.push((node) {nx,ny,x.step + 1,x.t1+1,x.t2});
				if(nx == tx && ny == ty && check(q.back(),ans)) {
					ans = q.back();
				}
			}
			else {
				if(vis[nx][ny][x.t1][x.t2]) {
					continue;
				}
				vis[nx][ny][x.t1][x.t2] = 1;
				q.push((node) {nx,ny,x.step + 1,x.t1,x.t2});
				if(nx == tx && ny == ty && check(q.back(),ans)) {
					ans = q.back();
				}
			}
		}
		for(int i = 0;i<4;i++) {
			int nx = x.x + dx[i] * d;
			int ny = x.y + dy[i] * d;
			if(nx < 1 || ny < 1 || nx > n || ny > m || army[nx][ny]) {
				continue;
			}
			if(lk[nx][ny]) {
				if(x.t1 >= c1 || x.t2 >= c2 || vis[nx][ny][x.t1 + 1][x.t2 + 1]) {
					continue;
				}
				vis[nx][ny][x.t1 + 1][x.t2 + 1] = 1;
				q.push((node){nx,ny,x.step + 1,x.t1 + 1,x.t2 + 1});
				if(nx == tx && ny == ty && check(q.back(),ans)) {
					ans = q.back();
				}
			}
			else {
				if(x.t1 >= c2 || vis[nx][ny][x.t1][x.t2 + 1]) {
					continue;
				}
				vis[nx][ny][x.t1][x.t2 + 1] = 1;
				q.push((node){nx,ny,x.step + 1,x.t1,x.t2+1});
				if(nx == tx && ny == ty && check(q.back(),ans)) {
					ans = q.back();
				}
			}
		}
		q.pop();
	}
}
//
void diff(int x,int y,int k) {
	for(int i = 0;i<k;i++) {
		dif[max(1,x - i)][max(1,y - k + i + 1)]++;
		dif[max(1,x - i)][min(m,y + k - i - 1) + 1]--;
		dif[min(n,x + i)][max(1,y - k + i + 1)]++;
		dif[min(n,x + i)][min(m,y + k - i - 1) + 1]--;
	}
}

signed main() {
	//
	cin>>n>>m>>c1>>c2>>d;
    for(int i = 1;i<=n;i++) {
        for(int j = 1;j<=m;j++) {
            string s;//
            cin>>s;
            if(s[0] == 'S') {
                q.push(node{i,j,0,0,0});
            }
            else {
                if(s[0] == 'T') {
                    tx = i;
                    ty = j;
                }else {
                    if(s[0] == '.') {
                    }else {
                        int x = 0;
                        for(int k = 0;s[k];k++) {
                            x = (x << 1) + (x << 3) + (s[k] ^ '0');
                        }
                        army[i][j] = x;
                        diff(i,j,x);
                    }
                }
            }
        }
    }//
	for(int i =1;i<=n;i++) {
		int sum = 0;
		for(int j = 1;j<=m;j++) {
			sum += dif[i][j];
			if(sum > 0) {
				lk[i][j] = 1;
			}
		}
	}
	bfs();
	if(ans.x == 0) {
        cout<<-1<<'\n';
    }
    else {
        cout<<ans.step<<' '<<ans.t1<<' '<<ans.t2<<'\n';
    }
	return 0;
}
2023/8/22 10:35
加载中...