| 123456789101112 |
- #include <algorithm>
- #include <cstdint>
- #include <iostream>
- #include <queue>
- #include <string>
- #include <tuple>
- #include <utility>
- #include <vector>
- using namespace std;
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int id,T;cin>>id>>T;while(T--){int n,m;cin>>n>>m;vector<string>board(n);for(auto&s:board)cin>>s;vector<pair<int,int>>cell;vector<vector<int>>index(n,vector<int>(m,-1));int black=-1;vector<int>red;for(int i=0;i<n;++i)for(int j=0;j<m;++j)if(board[i][j]!='#'){int z=cell.size();cell.push_back({i,j});index[i][j]=z;if(board[i][j]=='X')black=z;if(board[i][j]=='O')red.push_back(z);}int S=cell.size(),P=S*(S-1)/2;vector<vector<int>>pair_id(S,vector<int>(S,-1));vector<pair<int,int>>pairs;for(int a=0;a<S;++a)for(int b=a+1;b<S;++b)pair_id[a][b]=pair_id[b][a]=pairs.size(),pairs.push_back({a,b});auto encode=[&](int b,int p,int turn){return (b*P+p)*2+turn;};int total=S*P*2;vector<uint8_t>outcome(total);vector<int>distance(total),remaining(total),max_child(total);vector<vector<int>>red_move(S),black_move(S),black_pred(S);int dr[4]={-1,1,0,0},dc[4]={0,0,-1,1};for(int u=0;u<S;++u){auto[r,c]=cell[u];for(int z=0;z<4;++z){int x=r+dr[z],y=c+dc[z];if(0<=x&&x<n&&0<=y&&y<m&&index[x][y]>=0)red_move[u].push_back(index[x][y]);}for(int z:{0,2,3}){int x=r+dr[z],y=c+dc[z];if(0<=x&&x<n&&0<=y&&y<m&&index[x][y]>=0)black_move[u].push_back(index[x][y]);}int x=r+1;if(x<n&&index[x][c]>=0)black_pred[u].push_back(index[x][c]);for(int z:{2,3}){int y=c+dc[z];if(0<=y&&y<m&&index[r][y]>=0)black_pred[u].push_back(index[r][y]);}}
- using Item=pair<int,int>;priority_queue<Item,vector<Item>,greater<Item>>pq;for(int b=0;b<S;++b)for(int p=0;p<P;++p){auto[r1,r2]=pairs[p];for(int turn=0;turn<2;++turn){int st=encode(b,p,turn);bool terminal=false;if(cell[b].first==0){outcome[st]=turn==1?1:2;terminal=true;}else if(b==r1||b==r2){outcome[st]=2;terminal=true;}int deg=0;if(!terminal){if(turn==0){for(int v:red_move[r1])if(v!=r2)++deg;for(int v:red_move[r2])if(v!=r1)++deg;}else deg=black_move[b].size();remaining[st]=deg;if(deg==0){outcome[st]=2;terminal=true;}}if(terminal)pq.push({0,st});}}
- auto predecessors=[&](int st,auto emit){int turn=st%2,z=st/2,p=z%P,b=z/P;auto[r1,r2]=pairs[p];if(turn==0){for(int pb:black_pred[b])emit(encode(pb,p,1));}else{for(int prev:red_move[r1])if(prev!=r2){int a=min(prev,r2),c=max(prev,r2);emit(encode(b,pair_id[a][c],0));}for(int prev:red_move[r2])if(prev!=r1){int a=min(prev,r1),c=max(prev,r1);emit(encode(b,pair_id[a][c],0));}}};while(!pq.empty()){auto[dist,st]=pq.top();pq.pop();if(dist!=distance[st])continue;predecessors(st,[&](int pre){if(outcome[pre])return;if(outcome[st]==2){outcome[pre]=1;distance[pre]=dist+1;pq.push({distance[pre],pre});}else{--remaining[pre];max_child[pre]=max(max_child[pre],dist);if(remaining[pre]==0){outcome[pre]=2;distance[pre]=max_child[pre]+1;pq.push({distance[pre],pre});}}});}int a=min(red[0],red[1]),c=max(red[0],red[1]),start=encode(black,pair_id[a][c],0);if(!outcome[start])cout<<"Tie\n";else if(outcome[start]==1)cout<<"Red "<<distance[start]<<'\n';else cout<<"Black "<<distance[start]<<'\n';}}
|
