http://www.bnuoj.com/bnuoj/problem_show.php?pid=3017很是奇怪，晚上交一直TLE，優化了很久都無效，今天把優化都刪了，直接交，奇跡般的A了。。
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#define LEN 1010
char mp[LEN][LEN];
int m, n;
int k;
int d[4][2] = 
{0, 1, 0, -1, 1, 0, -1, 0};
int canWalk(int x, int y, char c)
{
if(x >= 0 && x < m && y >= 0 && y < n && mp[x][y] == c)
return 1;
return 0;
}
void DFS(int x, int y, char c)
{
int i, j;
for(i = 0; i < 4; i++)
{
int x1 = x + d[i][0];
int y1 = y + d[i][1];
if(canWalk(x1, y1, c))
{
mp[x1][y1] = ' ';
DFS(x1, y1, c);
}
}
}
void move()
{
int i, j;
int t;
for(i = 0; i < m; i++)//move left
{
t = 0;
for(j = 0; j < n; j++)
if(mp[i][j] != ' ')
mp[i][t++] = mp[i][j];
for(j = t; j < n; j++)
mp[i][j] = ' ';
}
for(i = 0; i < n; i++)//move down
{
t = m - 1;
for(j = m - 1; j >= 0; j--)
if(mp[j][i] != ' ')
mp[t--][i] = mp[j][i];
for(j = t; j >= 0; j--)
mp[j][i] = ' ';
}
}
void Out()
{
int i, j;
printf("mp[][] = \n");
for(i = 0; i < m; i++)
{
for(j = 0; j < n; j++)
printf("%c", mp[i][j]);
putchar(10);
}
}
int isBlackLine(int r)
{
int i, j;
for(i = 0; i < n; i++)
if(mp[r][i] != ' ')
return 0;
return 1;
}
int main()
{
int i, j;
int count = 1;
int x, y;
while(scanf("%s", mp[0]) != EOF)
{
i = 0;
getchar();
while(!isdigit(mp[i][0]))
{
gets(mp[++i]);
}
n = strlen(mp[0]);
m = i;
sscanf(mp[i], "%d", &k);
int bl = 0;
for(i = 0; i < k; i++)
{
scanf("%d%d", &x, &y);
int x0 = x + bl - 1;
int y0= y - 1;
int c = mp[x0][y0];
mp[x0][y0] = ' ';
DFS(x0, y0, c);
move();
bl = 0;
for(j = 0; j < m; j++)
if(mp[j][0] == ' ')
bl++;
}
printf("Test case #%d:\n", count++);
for(i = 0; i < m; i++)
{
for(j = 0; j < n; j++)
if(mp[i][j] != ' ')
putchar(mp[i][j]);
if(mp[i][0] != ' ')
putchar(10);
}
}
//system("pause");
return 0;
}
posted on 2012-09-01 11:05
小鼠標 閱讀(225)
評論(0) 編輯 收藏 引用 所屬分類:
網選訓練