The Same Game
【题目链接】The Same Game
【题目类型】模拟
&题解：
写这种模拟题要看心态啊,还要有足够的时间,必须仔细读题,一定要写一步,就调试一步.
这题我没想到的就是退出循环的条件,之后问了别人才知道:只要所有联通块的节点全是1,或者全部消掉了,就break.
注意:dfs的结束条件在最上面的,所以4个方向循环的时候不用特判,dfs一定要写vis标记
&代码：
#include <cstdio>
#include <bitset>
#include <iostream>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
const int maxn= 30 +9;
string s[maxn];
int n=10,m=15,vis[maxn][maxn];
struct pn
{
int x,y;
};
void dfs(int x,int y,char c,int& t)
{
if(x<0||x>=n||y<0||y>=m||vis[x][y]) return;
if(s[x][y]!=c) return;
t++;
vis[x][y]=1;
for(int i=-1;i<2;i++){
for(int j=-1;j<2;j++) if(!i^!j){
dfs(x+i,y+j,c,t);
}
}
}
void dfs2(int x,int y,char c)
{
if(x<0||x>=n||y<0||y>=m||vis[x][y]) return;
if(s[x][y]!=c) return;
s[x][y]='.';
vis[x][y]=1;
for(int i=-1;i<2;i++){
for(int j=-1;j<2;j++) if(!i^!j){
dfs2(x+i,y+j,c);
}
}
}
int K;
vector<int> vi;
bool allem(int y)
{
for(int i=0;i<n;i++){
if(s[i][y]!='.')
return false;
}
return true;
}
void smove()
{
//down
for(int j=0;j<m;j++){
for(int i=n-1;i>=0;i--){
if(s[i][j]=='.'){
for(int k=i;k>=0;k--){
if(s[k][j]!='.'){
swap(s[i][j],s[k][j]);
break;
}
}
}
}
}
//left
for(int j=0;j<m;j++){
if(allem(j)){
for(int k=j;k<m;k++){
if(!allem(k)){
for(int i=0;i<n;i++)
swap(s[i][j],s[i][k]);
break;
}
}
}
}
}
int okw()
{
int ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
if(s[i][j]!='.')
ans++;
}
return ans;
}
int main()
{
// ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
freopen("E:1.txt","r",stdin);
// freopen("E:2.txt","w",stdout);
int T; cin>>T;
while(T--){
ll fin=0;
for(int i=0;i<n;i++){
cin>>s[i];
}
printf("Game %d:
",++K);
int KK=0;
for(;1;){
vi.clear();
memset(vis,0,sizeof(vis));
int num=0,J=0;
pn p;
char CC;
for(int j=0;j<m;j++)
for(int i=n-1;i>=0;i--) if(!vis[i][j]&&s[i][j]!='.'){
int t=0;
dfs(i,j,s[i][j],t);
J++;
if(t<=1) continue;
vi.push_back(t);
// if(o==5){
// printf("t=%d===
",t);
// printf("i=%d j=%d
",i,j);
// }
if(t>num){
CC=s[i][j];
p.x=i,p.y=j;
num=t;
}
else if(t==num){
if(j<p.y&&i>p.x){
CC=s[i][j];
p.x=i,p.y=j;
}
}
}
// cout<<num<<endl;
// cout<<p.x<<','<<p.y<<endl;
// cout<<CC<<endl;
memset(vis,0,sizeof(vis));
if(vi.empty()||okw()==0){
break;
}
dfs2(p.x,p.y,CC);
// for(int i=0;i<n;i++){
// cout<<s[i]<<endl;
// }
printf("Move %d at (%d,%d): removed %d balls of color %c, got %lld points.
",++KK,n-p.x,p.y+1,num,CC,(ll)(num-2)*(num-2));
fin+=(ll)(num-2)*(num-2);
smove();
// for(int i=0;i<n;i++){
// cout<<s[i]<<endl;
// }
// for(auto i:vi)
// cout<<i<<" ";
// cout<<endl;
}
if(!okw()){
fin+=1000;
}
printf("Final score: %lld, with %d balls remaining.
",fin,okw());
if(K!=n) puts("");
}
return 0;
}