http://acm.pku.edu.cn/JudgeOnline/problem?id=1027
Код:
#include <stdio.h> #include <string.h> #define MAXC 15 #define MAXR 10 enum {TAKE=1,FIND = 2}; const int dd[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; char map[MAXR+2][MAXC+2]; int vis[MAXR+2][MAXC+2]; int score; int move(int x,int y,int mode); void shift(); int find(int &x,int &y); int main() { int task; int i,j,k,l,o; scanf("%d",&task); k = 0; while (task--) { printf("Game %d:\n\n",++k); score = 0; o = 0; for (i = MAXR - 1; i >= 0; i--) scanf("%s",map[i]); memset(vis,0,sizeof(vis)); while ( (l = find(i,j)) > 1 ) { printf("Move %d at (%d,%d): removed %d balls of color %c, got %d points.\n", ++o,i+1,j+1,l,map[i][j],(l-2)*(l-2)); memset(vis,0,sizeof(vis)); move(i,j,TAKE); shift(); score += (l-2)*(l-2); memset(vis,0,sizeof(vis)); } o = 0; for (i = 0; i < MAXR; i++) for (j = 0; j < MAXC; j++) if (map[i][j]) o++; if (!o) score += 1000; printf("Final score: %d, with %d balls remaining.\n\n",score,o); } return 0; } int move(int x,int y,int mode) { int i,j,k,l; if (vis[x][y]) return 0; vis[x][y] = 1; l = 1; for (k = 0; k < 4; k++) { i = x + dd[k][0]; j = y + dd[k][1]; if (i < 0 || i>= MAXR || j < 0 || j >= MAXC) continue; if (map[i][j] != map[x][y]) continue; l += move(i,j,mode); } if (mode == TAKE) map[x][y] = 0; return l; } int find(int &x,int &y) { int i,j,k,l; l = 1; for (j = 0; j < MAXC; j++) for (i = 0; i < MAXR; i++) if (map[i][j] && !vis[i][j]) { k = move(i,j,FIND); if (k > l) { l = k; x = i; y = j; } } return l; } void shift() { int i,j,k,l; for (j = 0; j < MAXC; j++) { i = 0; while (i < MAXR) { if (map[i][j]) { i++; continue;} for (k = i+1; k < MAXR; k++) map[k-1][j] = map[k][j]; map[MAXR-1][j] = 0; k = i; while (!map[k][j] && k < MAXR) k++; if (k == MAXR) break; } } j = 0; while (j < MAXC) { if (map[0][j]) { j++; continue;} for (k = j + 1; k < MAXC; k++) for (i = 0; i < MAXR; i++) map[i][k-1] = map[i][k]; for (i = 0; i < MAXR;i++) map[i][MAXC-1] = 0; k = j; while (!map[0][k] && k < MAXC) k++; if (k == MAXC) break; } }