---
# System prepended metadata

title: Facebook Hacker Cup 2021資格賽

---

# Facebook Hacker Cup 2021資格賽
想說無聊寫看看，發現有題好像我能寫出來，然後就試著寫看看了。
但是還是沒成功，大概對8,9成吧。

## Problem B: Xs and Os
![](https://i.imgur.com/xuGbLox.png)
![](https://i.imgur.com/V1QAbkE.png)
![](https://i.imgur.com/jF6KyeD.png)
**input**
```
8
2
XO
..
2
X.
.O
3
...
...
...
3
.OX
X..
..O
3
OXO
X.X
OXO
3
.XO
O.X
XO.
4
X...
.O.O
.XX.
O.XO
5
OX.OO
X.XXX
OXOOO
OXOOO
XXXX.
```
**output**
```
Case #1: 1 1
Case #2: 1 2
Case #3: 3 6
Case #4: 2 2
Case #5: 1 1
Case #6: Impossible
Case #7: 2 2
Case #8: 1 2
```
## pB 想法
覺得既然只要看直的跟橫的就好，那就分開一行一行看。
```cpp=
for(int j=0;j<m;j++){	
	for(int k=0;k<m;k++){
		if(a[j][k]==0)t++;
		else if(a[j][k]==1)x++;
		else o++;
	}
}
```
分別去算X,O,.的數量，只要O的數量不為0就不要看那行(因為不能連線)，如果O=0再去判斷還有幾個格子才能連線。
因為最後結果是要求填最少的X以及在填最少的X下時有幾種方法，所以只要保留最小的行動以及總和就好，更多的格子就不用去判斷。
```cpp=
if(o==0){
	if(t!=0&&t<min){
		min=t;
		sum=1;
	}
	else if(t==min){
		sum++;
	}
}
```
最後綜合出來的程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
//by icerain
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m,min=100,t=0,sum=0,x=0,o=0;
string s;
int a[50][50];
bool test=true;
cin>>n;
for(int i=0;i<n;i++){
	cin>>m;
	a[m][m]={};
	for(int j=0;j<m;j++){
		cin>>s;
		for(int k=0;k<m;k++){
			if(s[k]=='X')a[j][k]=1;
			else if(s[k]=='O')a[j][k]=2;
			else a[j][k]=0;
		}
	}
	for(int j=0;j<m;j++){	
		for(int k=0;k<m;k++){
			if(a[j][k]==0)t++;
			else if(a[j][k]==1)x++;
			else o++;
		}
		if(o==0){
			if(t!=0&&t<min){
				min=t;
				sum=1;
			}
			else if(t==min){
				sum++;
			}
		}
		o=0;
		x=0;
		t=0;
	}
	for(int k=0;k<m;k++){	
		for(int j=0;j<m;j++){
			if(a[j][k]==0)t++;
			else if(a[j][k]==1)x++;
			else o++;
		}	
		if(o==0){
			if(t!=0&&t<min){
				min=t;
				sum=1;
			}
			else if(t==min){
				sum++;
			}
		}
		o=0;
		x=0;
		t=0;
	}
	if(min!=100&sum!=0)cout<<min<<" "<<sum<<endl;
	else cout<<"Impossible"<<endl;
	min=100;
	sum=0;
}

return 0;
}
```
