POJ3467(예정)

Cross Counting
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 size k centered at the cell (x,y) iff all cells lying in the x-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 color c. (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
POJ Monthly--2007.11.25 , Yang Yi
제목이 선단수 냄새가 나는 것 같아서 내 선단수 능력에 한계가 있다.
N, M이 모두 매우 적고 O(N*M*(N+M)로 사전 처리됩니다.
업데이트할 때마다바뀐 것은 십자가다.따라서 업데이트는 O(N+M)개의 업데이트가 필요합니다.
나는 바깥쪽에 보초를 한 층 더 쳤다.쓰기가 비교적 원활하다.

/***********************************************************
	> OS     : Linux 3.13.0-24-generic (Mint-17)
	> Author : yaolong
	> Mail   : [email protected]
	> 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
", 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;
}

판권 성명: 본고의 블로그 오리지널 글, 블로그는 동의 없이 전재할 수 없습니다.