zoj 3646 Matrix Transformer

zoj 3646 Matrix Transformer

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<string>#include<cmath>#define N 310using namespace std;bool Map[N][N];bool vis[N];int linked[N];int n;bool dfs(int u){ if(u == -1) return false; int v; for(v=0;v<n;v++) if(!vis[v] && Map[u][v]) { vis[v] = true; if(linked[v] == -1 || dfs(linked[v])) { linked[v] = u; return true; } } return false;}int main(){ int i,j; while(scanf("%d",&n)==1) { memset(Map,0,sizeof(Map)); memset(linked,-1,sizeof(linked)); char tmp; getchar(); for(i=0;i<n;i++) { for(j=0;j<n;j++) { tmp = getchar(); if(tmp == 'U') Map[i][j] = true; } getchar(); } int mapping = 0; for(i=0;i<n;i++) { memset(vis,0,sizeof(vis)); if(dfs(i)) mapping ++; } if(mapping < n) cout << "NO" << endl; else cout << "YES" << endl; } return 0;}