首页 > 代码库 > POJ3467（预处理）
POJ3467（预处理）
| Time Limit: 1000MS | Memory Limit: 131072K | |
| Total Submissions: 1331 | Accepted: 375 |
Description
Given a N × M grid with different colors on each cell, your task is to calculate the total amount of crosses of a specific color. We say there exists a cross of sizek centered at the cell (x,y) iff all cells lying in thex-th row or the y-th column and within a distance of k from (x,y) share the same color. Note that if two crosses have the same center but different sizes we consider they are distinct. Unfortunately, the color of each cell may varies by time and you have to respond to all the queries.
Input
There are four integers, N, M, C, Q, in the first line. (1 ≤N, M, C ≤ 100, 1 ≤ Q ≤ 10000)
The next N lines each contains M integers between 1 and C which describe the color of cells.
The following Q lines each has either the form "C i j k" indicating to change the color of cell (i,j) into k, or the form "Q c" indicating to query the total amount of crosses of colorc. (1 ≤ i ≤ N, 1 ≤ j ≤ M, 1 ≤ k,c ≤ C)
Output
Output the answer to each query.
Sample Input
5 5 3 6 1 3 2 3 1 3 3 2 3 3 2 2 2 2 2 3 3 2 3 3 1 3 2 3 1 Q 1 Q 2 Q 3 C 2 3 3 C 3 2 3 Q 3
Sample Output
0 2 0 1
Source
题目看起来有线段树的味道，我线段树能力有限。
发现N,M都很少，用O(N*M*(N+M))做预处理。
对于每次更新，改变的是十字架。所以更新需要O(N+M)个更新。
我在外层加了一层哨兵，写起来比较顺畅。
/***********************************************************
> OS : Linux 3.13.0-24-generic (Mint-17)
> Author : yaolong
> Mail : dengyaolong@yeah.net
> Time : 2014年10月15日 星期三 07时11分26秒
**********************************************************/
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
const int N = 205;
int mp[N][N];
int cnt[N][N];
int color[N];
void update ( int i, int j )
{
cnt[i][j] = 0;
for ( int k = 1;; k++ )
{
if ( mp[i + k][j] == mp[i][j] && mp[i - k][j] == mp[i][j] && mp[i][j + k] == mp[i][j] && mp[i][j - k] == mp[i][j] )
{
cnt[i][j]++;
}
else
{
return ;
}
}
}
int main()
{
int n, m, c, q;
while ( scanf ( "%d%d%d%d", &n, &m, &c, &q ) != EOF )
{
int i, j, k;
memset ( color, 0, sizeof ( color ) );
memset ( mp, 63, sizeof ( mp ) );
memset ( cnt, 0, sizeof ( cnt ) );
for ( i = 1; i <= n; i++ )
{
for ( j = 1; j <= m; j++ )
{
scanf ( "%d", &mp[i][j] );
}
}
for ( i = 1; i <= n; i++ )
{
for ( j = 1; j <= m; j++ )
{
update ( i, j );
color[mp[i][j]] += cnt[i][j];
}
}
char tmp;
while ( q-- )
{
scanf ( " %c", &tmp );
if ( tmp == 'Q' )
{
scanf ( "%d", &i );
printf ( "%d\n", color[i] );
}
else
{
scanf ( "%d%d%d", &i, &j, &k );
if ( mp[i][j] == k )
{
continue;
}
color[mp[i][j]] -= cnt[i][j];
mp[i][j] = k;
update ( i, j );
color[mp[i][j]] += cnt[i][j];
//cout<<cnt[i][j]<<" "<<i<<j<<endl;
for ( int ak = 1; ak <= n; ak++ )
{
if ( i != ak )
{
color[mp[ak][j]] -= cnt[ak][j]; //减掉
update ( ak, j );
color[mp[ak][j]] += cnt[ak][j];
}
}
for ( int ak = 1; ak <= m; ak++ )
{
if ( j != ak )
{
color[mp[i][ak]] -= cnt[i][ak]; //减掉
update ( i, ak );
color[mp[i][ak]] += cnt[i][ak];
}
}
}
}
}
return 0;
}
POJ3467（预处理）