题目大意
给定 n*m 的棋盘,棋盘上有 4 种类型的边,分别代表不可通行、只能走一步、只能一直沿一个方向往前走和可以任意走。棋子有两种颜色和等级,棋子间可以吃子,规定只能吃颜色不同且等级不高于自己的棋子,且吃完子后不能继续向前走。同时规定每次走子时经过的边类型必须相同。初始棋盘是空的,有 q 次操作,每次往棋盘上放一个棋子,问这个棋子能走到多少个格子。
解题思路(暴力)
很朴素的思想,对于每次放入的棋子都用bfs暴力模拟一遍,每一种边都遍历一遍,这样对于每个点,最多只会遍历棋盘上的每一条边,也就是2mn,总复杂度O(2mnq),对于前6个点的nm<5000和q<2000还是很轻松的,对于7-8两个测试点,因为只有普通路,每次遍历只会遍历4条边,所以是O(4*q)轻松过
思路二(12-14测试点)
因为只有普通和互通道路,所以我们可以先把所有的互通边加入并查集,并查集的大小不就是这个点通过互通道路到达的点数吗。可接下来我们会发现一个问题:如果棋子把路拦起来了怎么办?最好想的情况,一个棋子放在了4个棋子的中间,也就是它的四面都是棋子,那它最多只能走到这四个棋子的格子上,而它周围的边可能都在并查集里,那答案就会比真实值大很多
所以我们要换思路,假如我们先把所有的棋子都加入到棋盘中,然后从最后一个棋子开始爆搜不就好了吗?
代码(未修改完
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template <typename T>
inline void read1(T &x)
{
T f = 0;
x = 1;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-') x = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
f = (f << 3) + (f << 1) + (c ^ 48);
c = getchar();
}
x *= f;
}
typedef long long LL;
const int N=5010,INF=0x3f3f3f3f;
int n,m,q;
int c1,l1,x1,y1;
int c[N],l[N];
int x[N][N],y[N][N],a[N][N];
int ans=-1;
int fx[4]={1,-1,0,0};
int fy[4]={0,0,1,-1};
bool vis[N][N][2];
inline bool check(int nowx,int nowy,int x0,int y0,int flag){
int tox=nowx+x0,toy=nowy+y0;
if(flag==3&&vis[tox][toy][1]) return false;
if(tox<1||tox>n||toy<1||toy>m) return false;
if(x0==1){
if(x[nowx][nowy]!=flag) return false;
}
else if(x0==-1){
if(x[nowx-1][nowy]!=flag) return false;
}
else if(y0==1){
if(y[nowx][nowy]!=flag) return false;
}
else{
if(y[nowx][nowy-1]!=flag) return false;
}
return true;
}
int read(){
char c=getchar();
while(c<'0'||c>'9') c=getchar();
if(c>='0'&&c<='9') return c-48;
}
void bfs(int nowx,int nowy,int flag,int face){
if(flag==3&&vis[nowx][nowy][1]) return;
if(a[nowx][nowy]){
int c0=c[a[nowx][nowy]],l0=l[a[nowx][nowy]];
if(c1==c0) return;
if(l1>=l0){
if(!vis[nowx][nowy][0]){
ans++;
}
}
vis[nowx][nowy][0]=1;
if(flag==3) vis[nowx][nowy][1]=1;
return;
}
if(!vis[nowx][nowy][0]) ans++;
vis[nowx][nowy][0]=1;
if(flag==3) vis[nowx][nowy][1]=1;
if(flag==1){
for(int i=0;i<4;i++){
if(!check(nowx,nowy,fx[i],fy[i],flag)) continue;
int tox=nowx+fx[i],toy=nowy+fy[i];
if(a[tox][toy]){
int c0=c[a[tox][toy]],l0=l[a[tox][toy]];
if(c1==c0) continue;
if(l1>=l0){
if(!vis[tox][toy][0]){
ans++;
vis[tox][toy][0]=1;
}
}
continue;
}
vis[tox][toy][0]=1;
ans++;
}
}
else if(flag==2){
if(face==0){//face==-2 -1 1 2 0 down up left right
for(int i=0;i<4;i++){
if(!check(nowx,nowy,fx[i],fy[i],flag)) continue;
int tox=nowx+fx[i],toy=nowy+fy[i];
if(fx[i]==1) face=2;
else if(fx[i]==-1) face=1;
else if(fy[i]==1) face=-1;
else face=-2;
bfs(tox,toy,flag,face);
}
}
else if(face==-2){
if(check(nowx,nowy,0,-1,flag)) bfs(nowx,nowy-1,flag,face);
}
else if(face==-1){
if(check(nowx,nowy,0,1,flag)) bfs(nowx,nowy+1,flag,face);
}
else if(face==1){
if(check(nowx,nowy,-1,0,flag)) bfs(nowx-1,nowy,flag,face);
}
else if(check(nowx,nowy,1,0,flag)) bfs(nowx+1,nowy,flag,face);
}
else{
for(int i=0;i<4;i++){
if(!check(nowx,nowy,fx[i],fy[i],flag)) continue;
int tox=nowx+fx[i],toy=nowy+fy[i];
bfs(tox,toy,flag,0);
}
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
memset(a,0,sizeof(a));
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++){
for(int j=1;j<m;j++){
y[i][j]=read();
//printf("%d %d %d\n",i,j,y[i][j]);
}
}
//puts("");
for(int i=1;i<n;i++){
for(int j=1;j<=m;j++){
x[i][j]=read();
//printf("%d %d %d\n",i,j,x[i][j]);
}
}
for(int i=1;i<=q;i++){
read1(c1);read1(l1);read1(x1);read1(y1);
//scanf("%d%d%d%d",&c1,&l1,&x1,&y1);
ans=-1;
memset(vis,0,sizeof(vis));
for(int j=1;j<=3;j++){
bfs(x1,y1,j,0);
}
a[x1][y1]=i;c[i]=c1;l[i]=l1;
printf("%d\n",ans);
}
}
return 0;
}