/*
{
######################
# Author #
# Gary #
# 2021 #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
// int x=0;
// char ch=getchar();
// while(ch<‘0‘||ch>‘9‘){
// ch=getchar();
// }
// while(ch>=‘0‘&&ch<=‘9‘){
// x=(x<<1)+(x<<3)+(ch^48);
// ch=getchar();
// }
// return x;
//}
#define x1 kokokok
#define x2 okkkkkk
#define y1 kiiiiii
#define y2 kikkkkk
const int INF=0x3f3f3f3f;
/*}
*/
int tim[6][6][6][6][2][2][31][31];
bool sta[6][6][6][6][2][2][31][31];
int deg[6][6][6][6][2][2][31][31];
int x1,y1,x2,y2,xt,yt,n;
int wall[6][6][4];
int walk[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
string maze[6*3];
char maze2[6][6];
vector<pair<bool,pair<short,short> > > walls;
#define check(a,b) (a<n&&a>=0&&b<n&&b>=0)
struct Tmp{
int a,b,c,d,e,f,g,h;
Tmp(){}
Tmp(int A,int B,int C,int D,int E,int F,int G,int H){
a=A,b=B,c=C,d=D,e=E,f=F,g=G,h=H;
}
bool operator == (Tmp oth){
return vector<int>{a,b,c,d,e,f,g,h}==vector<int>{oth.a,oth.b,oth.c,oth.d,oth.e,oth.f,oth.g,oth.h};
}
};
queue<Tmp> q;
void getpre(short X1,short Y1,short X2,short Y2,bool t1,bool t2,short s1,short s2,short x){
if(s1==s2&&s1!=30){
sta[X1][Y1][X2][Y2][t1][t2][s1][s2]=0;
deg[X1][Y1][X2][Y2][t1][t2][s1][s2]=30;
return ;
}
if(t1&&t2){
sta[X1][Y1][X2][Y2][t1][t2][s1][s2]=0;
deg[X1][Y1][X2][Y2][t1][t2][s1][s2]=30;
return ;
}
if(X1==X2&&Y1==Y2){
sta[X1][Y1][X2][Y2][t1][t2][s1][s2]=0;
deg[X1][Y1][X2][Y2][t1][t2][s1][s2]=30;
return ;
}
int Time=tim[X1][Y1][X2][Y2][t1][t2][s1][s2]+1;
if(x==-1){
if(sta[X1][Y1][X2][Y2][t1][t2][s1][s2]){
rep(i,4){//move
bool havewall=0;
int nx,ny;
nx=X2+walk[i][0];
ny=Y2+walk[i][1];
if(!check(nx,ny)) continue;
if(wall[X2][Y2][i]!=-1&&s1!=wall[X2][Y2][i]&&s2!=wall[X2][Y2][i]) havewall=true;
if(wall[nx][ny][i^1]!=-1&&s1!=wall[nx][ny][i^1]&&s2!=wall[nx][ny][i^1]) havewall=true;
if(!havewall){
if(maze2[X2][Y2]==‘*‘&&t2){
if(!sta[nx][ny][X1][Y1][0][t1][s2][s1]&&!(--deg[nx][ny][X1][Y1][0][t1][s2][s1])){
tim[nx][ny][X1][Y1][0][t1][s2][s1]=Time;
q.push(Tmp(nx,ny,X1,Y1,0,t1,s2,s1));
}
if(!sta[nx][ny][X1][Y1][1][t1][s2][s1]&&!(--deg[nx][ny][X1][Y1][1][t1][s2][s1])){
tim[nx][ny][X1][Y1][1][t1][s2][s1]=Time;
q.push(Tmp(nx,ny,X1,Y1,1,t1,s2,s1));
}
}
else{
if(!sta[nx][ny][X1][Y1][t2][t1][s2][s1]&&!(--deg[nx][ny][X1][Y1][t2][t1][s2][s1])){
tim[nx][ny][X1][Y1][t2][t1][s2][s1]=Time;
q.push(Tmp(nx,ny,X1,Y1,t2,t1,s2,s1));
}
}
}
}
//stay
if(!sta[X2][Y2][X1][Y1][t2][t1][s2][s1]&&!(--deg[X2][Y2][X1][Y1][t2][t1][s2][s1])){
tim[X2][Y2][X1][Y1][t2][t1][s2][s1]=Time;
q.push(Tmp(X2,Y2,X1,Y1,t2,t1,s2,s1));
}
//shoot
if(s2!=30)
rep(i,4){
bool havewall=0;
int nx,ny;
nx=X2+walk[i][0];
ny=Y2+walk[i][1];
if(wall[X2][Y2][i]==s2) havewall=true;
if(check(nx,ny)&&wall[nx][ny][i^1]==s2&&(wall[X2][Y2][i]==-1||wall[X2][Y2][i]==s1)) havewall=true;
if(havewall){
if(!sta[X2][Y2][X1][Y1][t2][t1][30][s1]&&!(--deg[X2][Y2][X1][Y1][t2][t1][30][s1])){
tim[X2][Y2][X1][Y1][t2][t1][30][s1]=Time;
q.push(Tmp(X2,Y2,X1,Y1,t2,t1,30,s1));
}
}
}
}
else{
rep(i,4){//move
bool havewall=0;
int nx,ny;
nx=X2+walk[i][0];
ny=Y2+walk[i][1];
if(!check(nx,ny)) continue;
if(wall[X2][Y2][i]!=-1&&s1!=wall[X2][Y2][i]&&s2!=wall[X2][Y2][i]) havewall=true;
if(wall[nx][ny][i^1]!=-1&&s1!=wall[nx][ny][i^1]&&s2!=wall[nx][ny][i^1]) havewall=true;
if(!havewall){
if(maze2[X2][Y2]==‘*‘&&t2){
if(!sta[nx][ny][X1][Y1][0][t1][s2][s1]){
sta[nx][ny][X1][Y1][0][t1][s2][s1]=1;
tim[nx][ny][X1][Y1][0][t1][s2][s1]=Time;
if(nx==x1&&ny==y1&&X1==x2&&Y1==y2&&!t1&&s1==30&&s2==30){
printf("Win %d\nM",Time);
if(i==1) printf("6");
if(i==0) printf("4");
if(i==3) printf("2");
if(i==2) printf("8");
exit(0);
}
q.push(Tmp(nx,ny,X1,Y1,0,t1,s2,s1));
}
if(!sta[nx][ny][X1][Y1][1][t1][s2][s1]){
sta[nx][ny][X1][Y1][1][t1][s2][s1]=1;
tim[nx][ny][X1][Y1][1][t1][s2][s1]=Time;
q.push(Tmp(nx,ny,X1,Y1,1,t1,s2,s1));
}
}
else{
if(!sta[nx][ny][X1][Y1][t2][t1][s2][s1]){
sta[nx][ny][X1][Y1][t2][t1][s2][s1]=1;
tim[nx][ny][X1][Y1][t2][t1][s2][s1]=Time;
if(nx==x1&&ny==y1&&X1==x2&&Y1==y2&&!t2&&!t1&&s1==30&&s2==30){
printf("Win %d\nM",Time);
if(i==1) printf("6");
if(i==0) printf("4");
if(i==3) printf("2");
if(i==2) printf("8");
exit(0);
}
q.push(Tmp(nx,ny,X1,Y1,t2,t1,s2,s1));
}
}
}
}
//stay
if(!sta[X2][Y2][X1][Y1][t2][t1][s2][s1]){
sta[X2][Y2][X1][Y1][t2][t1][s2][s1]=1;
tim[X2][Y2][X1][Y1][t2][t1][s2][s1]=Time;
if(X2==x1&&Y2==y1&&X1==x2&&Y1==y2&&!t1&&!t2&&s1==30&&s2==30){
printf("Win %d\nM5\n",Time);
exit(0);
}
q.push(Tmp(X2,Y2,X1,Y1,t2,t1,s2,s1));
}
//shoot
if(s2!=30)
rep(i,4){
bool havewall=0;
int nx,ny;
nx=X2+walk[i][0];
ny=Y2+walk[i][1];
if(wall[X2][Y2][i]==s2) havewall=true;
if(check(nx,ny)&&wall[nx][ny][i^1]==s2&&(wall[X2][Y2][i]==-1||wall[X2][Y2][i]==s1)) havewall=true;
if(havewall){
if(!sta[X2][Y2][X1][Y1][t2][t1][30][s1]){
sta[X2][Y2][X1][Y1][t2][t1][30][s1]=1;
tim[X2][Y2][X1][Y1][t2][t1][30][s1]=Time;
if(X2==x1&&Y2==y1&&X1==x2&&Y1==y2&&!t1&&!t2&&s1==30){
printf("Win %d\nS",Time);
if(i==0) printf("6");
if(i==1) printf("4");
if(i==2) printf("2");
if(i==3) printf("8");
exit(0);
}
q.push(Tmp(X2,Y2,X1,Y1,t2,t1,30,s1));
}
}
}
}
}
else{
rep(i,4){//move
bool havewall=0;
int nx,ny;
nx=X2+walk[i][0];
ny=Y2+walk[i][1];
if(!check(nx,ny)) continue;
if(wall[X2][Y2][i]!=-1&&s1!=wall[X2][Y2][i]&&s2!=wall[X2][Y2][i]) havewall=true;
if(wall[nx][ny][i^1]!=-1&&s1!=wall[nx][ny][i^1]&&s2!=wall[nx][ny][i^1]) havewall=true;
if(!havewall){
if(maze2[X2][Y2]==‘*‘&&t2) deg[nx][ny][X1][Y1][0][t1][s2][s1]++,deg[nx][ny][X1][Y1][1][t1][s2][s1]++;
else deg[nx][ny][X1][Y1][t2][t1][s2][s1]++;
}
}
//stay
deg[X2][Y2][X1][Y1][t2][t1][s2][s1]++;
//shoot
if(s2!=30)
rep(i,4){
bool havewall=0;
int nx,ny;
nx=X2+walk[i][0];
ny=Y2+walk[i][1];
if(wall[X2][Y2][i]==s2) havewall=true;
if(check(nx,ny)&&wall[nx][ny][i^1]==s2&&(wall[X2][Y2][i]==-1||wall[X2][Y2][i]==s1)) havewall=true;
if(havewall){
deg[X2][Y2][X1][Y1][t2][t1][30][s1]++;
}
}
}
}
void upd(short X1,short Y1,short X2,short Y2,bool t1,bool t2,short s1,short s2){
if(X1==x1&&Y1==y1&&X2==x2&&Y2==y2&&!t1&&!t2&&s1==30&&s2==30){
assert(sta[X1][Y1][X2][Y2][t1][t2][s1][s2]==0);
puts("Lose 1\nS5");
exit(0);
}
// cout<<X1<<" "<<Y1<<" "<<X2<<" "<<Y2<<" "<<t1<<‘ ‘<<t2<<" "<<s1<<" "<<s2<<endl;
getpre(X1,Y1,X2,Y2,t1,t2,s1,s2,-1);
}
int main(){
// cout<<(sizeof(tim)+sizeof(sta)+sizeof(deg))/1024/1024<<endl;
cin>>n;
getline(cin,maze[0]);
int tmpx,tmpy;
rep(i,n) rep(j,n) rep(k,4) wall[i][j][k]=-1;
rep(i,n*3){
getline(cin,maze[i]);
rep(j,n*3){
if(maze[i][j]==‘1‘) x1=i/3,y1=j/3;
if(maze[i][j]==‘2‘) x2=i/3,y2=j/3;
if(maze[i][j]==‘*‘) xt=i/3,yt=j/3;
tmpx=i/3,tmpy=j/3;
if(i%3==1&&j%3==1){
maze2[tmpx][tmpy]=maze[i][j];
}
if(maze[i][j]==‘|‘){
if(j%3==2){
wall[tmpx][tmpy][0]=walls.size();
walls.PB(II(0,II(tmpx,tmpy)));
}
if(j%3==0){
wall[tmpx][tmpy][1]=walls.size();
walls.PB(II(0,II(tmpx,tmpy-1)));
}
}
if(maze[i][j]==‘-‘){
if(i%3==2){
wall[tmpx][tmpy][2]=walls.size();
walls.PB(II(1,II(tmpx,tmpy)));
}
if(i%3==0){
wall[tmpx][tmpy][3]=walls.size();
walls.PB(II(1,II(tmpx-1,tmpy)));
}
}
}
}
// rep(i,n){
// rep(j,n) cout<<maze2[i][j];
// cout<<endl;
// }
// cout<<wall[0][2][2]<<endl;
rep(i,n) rep(j,n) rep(k,n) rep(l,n) rep(t1,2) rep(t2,2) rb(s1,0,30) rb(s2,0,30) getpre(i,j,k,l,t1,t2,s1,s2,1);
rep(i,n) rep(j,n) rep(k,n) rep(l,n) rep(t1,2) rep(t2,2) rb(s1,0,30) rb(s2,0,30){
bool ok=0;
if(t1&&t2) continue;
if(t1){
if(i==0){
if(wall[i][j][3]==-1||wall[i][j][3]==s1||wall[i][j][3]==s2) ok=1;
}
if(j==0){
if(wall[i][j][1]==-1||wall[i][j][1]==s1||wall[i][j][1]==s2) ok=1;
}
if(i==n-1){
if(wall[i][j][2]==-1||wall[i][j][2]==s1||wall[i][j][2]==s2) ok=1;
}
if(j==n-1){
if(wall[i][j][0]==-1||wall[i][j][0]==s1||wall[i][j][0]==s2) ok=1;
}
}
if(i==k){
int cnt=0;
rb(z,min(j,l),max(j,l)-1){
if(wall[i][z][0]!=-1&&s2!=wall[i][z][0]) cnt++;
}
rb(z,min(j,l)+1,max(j,l)){
if(wall[i][z][1]!=-1&&s2!=wall[i][z][1]) cnt++;
}
if(cnt==0&&s1==30) ok=1;
}
if(j==l){
int cnt=0;
rb(z,min(i,k),max(i,k)-1){
if(wall[z][j][2]!=-1&&s2!=wall[z][j][2]) cnt++;
}
rb(z,min(i,k)+1,max(i,k)){
if(wall[z][j][3]!=-1&&s2!=wall[z][j][3]) cnt++;
}
if(cnt==0&&s1==30) ok=1;
}
if(i==x1&&j==y1&&k==x2&&l==y2&&!t1&&!t2&&s1==30&&s2==30&&ok){
if(x1==x2&&y1<y2)
printf("Win 1\nS6\n");
if(x1==x2&&y1>y2)
printf("Win 1\nS4\n");
if(y1==y2&&x1<x2)
printf("Win 1\nS2\n");
if(y1==y2&&x1>x2)
printf("Win 1\nS8\n");
return 0;
}
if(ok){
q.push(Tmp(i,j,k,l,t1,t2,s1,s2));
// if(i==1&&j==2&&k==0&&l==2) cout<<t1<<" "<<t2<<" "<<s1<<‘ ‘<<s2<<endl;
sta[i][j][k][l][t1][t2][s1][s2]=1;
tim[i][j][k][l][t1][t2][s1][s2]=1;
}
}
while(!q.empty()){
Tmp f=q.front();
q.pop();
// if(f==Tmp(2,2,0,2,0,0,3,30)) cout<<"!"<<endl;
upd(f.a,f.b,f.c,f.d,f.e,f.f,f.g,f.h);
}
// cout<<deg[0][2][2][2][0][0][30][3]<<" "<<sta[0][2][2][2][0][0][30][3]<<endl;
puts("Draw");
return 0;
}
Ural 1555 Find the Treasure! 题解
原文：https://www.cnblogs.com/gary-2005/p/14717268.html