这道题wa了三次很可惜,其实很简单!
第一次是RE,32*32=1024,好丢人!
第二次是没注意,(x,y)表示y行x列,直接按照原有经验,搞成了x行y列!丢人!
第三次是双层for循环,j的那个内层循环只循环到n结束,正确的是应该到m结束!
这篇总结必然好好保存,写代码真的要认真!
代码:
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int N = 1100; int n, m, k; int g[35][35]; int cy[N], bmap[N][N]; bool vis[N]; bool dfs( int u ) { for ( int v = 0; v < n*m; ++v ) if ( !vis[v] && bmap[u][v] ) { vis[v] = 1; if ( cy[v] == -1 || dfs( cy[v] ) ) { cy[v] = u; return 1; } } return 0; } int match() { int res = 0; memset( cy, -1, sizeof(cy) ); for ( int i = 0; i < n*m; ++i ) { memset( vis, 0, sizeof(vis)); if ( dfs(i) ) res++; } return res; } int main() { while ( scanf("%d%d%d", &n, &m, &k) == 3 ) { memset( g, 0, sizeof(g) ); memset( bmap, 0, sizeof(bmap) ); int num = n*m; while ( k-- ) { int u, v; scanf("%d%d", &u, &v); u--, v--; g[v][u] = 1; num--; } for ( int i = 0; i < n; ++i ) for ( int j = 0; j < m; ++j ) { int u = i*m+j, v; if ( g[i][j] == 1 ) continue; if ( i > 0 && g[i-1][j] == 0 ) bmap[u][(i-1)*m+j] = 1; if ( j > 0 && g[i][j-1] == 0 ) bmap[u][i*m+j-1] = 1; if ( j < m-1 && g[i][j+1] == 0 ) bmap[u][i*m+j+1] = 1; if ( i < n-1 && g[i+1][j] == 0 ) bmap[u][(i+1)*m+j] = 1; } int ans = match(); //printf("%d", ans); if ( ans == num ) printf("YES\n"); else printf("NO\n"); } }