이분도 일치: Matrix Transformer
Time Limit: 2 Seconds
Memory Limit: 65536 KB
Alice and Bob meet again. This time they play a game named MATRIX TRANSFORMER.
They got an n * n board. Every grid has two positions, UP and DOWN. In this game you can push some amazing buttons to exchange any two rows or any two columns. Alice will win if she got the grids in the main diagonal line all UP.
But Alice finds that for some board, no matter how many times she tries, she cannot get the grids in the main diagonal line all UP. Now she asks you for help, tell her if she can win this board or not.
Input
There are several test cases. For each test case: The 1st line contains 1 integer n, indicating the size of the board. (1 ≤ n ≤ 200) The next n lines, each contains n characters. 'U' indicates the position UP, and 'D' indicates the position DOWN. There is no separation line between any two test cases.
Output
For each test case, you should print one line.You should print 'YES' if Alice can win, print 'NO' if not.
Sample Input
3
DUD
UDD
DDU
3
DUD
DUD
UDD
Sample Output
YES
NO
제목 대의: 행렬의 줄 교환열을 통해 대각선을 모두 U로 바꿀 수 있습니까?
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<set>
#define inf 110000000
#define M 10005
#define N 100005
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define LL long long
using namespace std;
const int MAXN = 440;
int uN,vN; //u,vÊýÄ¿
int g[MAXN][MAXN];//±àºÅÊÇ0~n-1µÄ
int linker[MAXN];
bool used[MAXN];
bool dfs(int u){
int v;
for(v=0;v<=vN;v++)
if(g[u][v]&&!used[v]){
used[v]=true;
if(linker[v]==-1||dfs(linker[v])){
linker[v]=u;
return true;
}
}
return false;
}
int hungary(){
int res=0;
int u;
memset(linker,-1,sizeof(linker));
for(u=0;u<=uN;u++){
memset(used,0,sizeof(used));
if(dfs(u)) res++;
}
return res;
}
int main(){
int n;
while(~scanf("%d", &n)){
int i, j, k;
char ch[210];
uN = n - 1;
vN = n - 1;
memset(g, 0, sizeof(g));
for(i = 0; i < n; i ++){
scanf("%s", ch);
for(j = 0; j < n; j ++){
if(ch[j] == 'U')
g[i][j] = 1;
}
}
//printf("ans = %d
", hungary());
if(hungary() == n){
printf("YES
");
}
else
printf("NO
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
cocos2d Lua 학습(一)ios에서 루아 함수 호출 및 전참 방법 lua 코드: 출력 결과: lua 호출 C++ 방법: add 함수: lua 코드: 출력 결과: 함수를 호출합니다. 함수를 호출하려면 다음 협의를 따르십시오. 우선, 호출할 함...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.