ÀÛ¼ºÀÏ : 15-08-02 11:19
¹®Á¦ Áú¹®
 ±Û¾´ÀÌ : ¹éµµ¿ø(do1006)
Á¶È¸ : 7,280  
   http://usaco.org/index.php?page=feb15results [4761]

USACO 2015 February Contest, Silver

Cow Hopscotch ¹®Á¦ÀÔ´Ï´Ù.

Just like humans enjoy playing the game of Hopscotch, Farmer John's cows have invented a variant of the game for themselves to play. Being played by clumsy animals weighing nearly a ton, Cow Hopscotch almost always ends in disaster, but this has surprisingly not deterred the cows from attempting to play nearly every afternoon.

The game is played on an R by C grid (2 <= R <= 100, 2 <= C <= 100), where each square is labeled with an integer in the range 1..K (1 <= K <= R*C). Cows start in the top-left square and move to the bottom-right square by a sequence of jumps, where a jump is valid if and only if

1) You are jumping to a square labeled with a different integer than your current square,

2) The square that you are jumping to is at least one row below the current square that you are on, and

3) The square that you are jumping to is at least one column to the right of the current square that you are on.

Please help the cows compute the number of different possible sequences of valid jumps that will take them from the top-left square to the bottom-right square.

INPUT FORMAT: (file hopscotch.in)

The first line contains the integers R, C, and K. The next R lines will each contain C integers, each in the range 1..K.

OUTPUT FORMAT: (file hopscotch.out)

Output the number of different ways one can jump from the top-left square to the bottom-right square, mod 1000000007.

SAMPLE INPUT:

4 4 4
1 1 1 1
1 3 2 1
1 2 4 1
1 1 1 1

SAMPLE OUTPUT:

5

ÇÁ·Î±×·¥À» ´ÙÀ½°ú °°ÀÌ ÀÛ¼ºÇߴµ¥

#include <stdio.h>
#define MOD 1000000007
int r,c,k;
long long int a[101][101];
long long int d[101][101];
int mod(int x){
    return (x+MOD)%MOD;
}
int main(){
    scanf("%d%d%d",&r,&c,&k);
    int i,j,l,m;
    for(i=0;i<r;i++)
        for(j=0;j<c;j++)
            fscanf(inf,"%lld",&a[i][j]);
    d[0][0] = 1;
    for(i=0;i<r;i++){
        for(j=0;j<c;j++){
            for(l=i+1;l<r;l++){
                for(m=j+1;m<c;m++){
                    if(a[i][j]!=a[l][m]) d[l][m] = mod(d[i][j]+d[l][m]);
                }
            }
        }
    }
    printf("%lld",d[r-1][c-1]);
    return 0;
}

4°³ test case¸¸ Á¤´äÀÌ Ãâ·ÂµÇ°í, ´Ù¸¥ test caseµéÀº Á¤´äÀÌ Ãâ·ÂµÇÁö ¾Ê½À´Ï´Ù.
Ç®ÀÌ¿¡¼­µµ À§¿Í À¯»çÇÏ°Ô ÄÚµùÀÌ µÇ¾î Àִµ¥, ¹«¾ùÀÌ ¹®Á¦ÀÎÁö Àß ¸ð¸£°Ú½À´Ï´Ù.

Ç®ÀÌ

The grid is big enough that it is not possible for us to merely try all possible paths.

We simply care about how many ways there are to get to a given square though. Let f(x,y)  be the number of ways there are to get to row x  and column y  . Note that f(x,y)  is simply the sum of all f(i,j)  where i<x  , j<y  , and the numbers in those squares don't match. This gives us an O(R 2 C 2 )  algorithm, which is fast enough for our purposes.


°¨»çÇÕ´Ï´Ù.



ÄĽºÄð 15-08-12 18:43
 
ÀÌ°÷¿¡¼­ ´äº¯µå¸± ³»¿ëÀº ¾Æ´Ñ°Å °°Áö¸¸ °£´ÜÇÏ°Ô »ìÆ캸¸é int mod(int x) ÀÌ ÇÔ¼ö¿¡ ¹®Á¦°¡ Àִ°ÍÀ¸·Î º¸ÀÔ´Ï´Ù.

±¸ÇØ¾ß ÇÏ´Â ´ë»óÀº ¸ðµÎ long long int ÇüÀε¥ ÀÌ ÇÔ¼ö¿¡¼­´Â int·Î ¹Þ¾Æ¼­ int·Î return Çϴ±º¿ä.
°è»êÇÏ´Â °úÁ¤¿¡¼­ Á¤¼öÀÇ ¹üÀ§¸¦ ³Ñ¾î°¥ ¼ö Àֱ⠶§¹®¿¡ Å« µ¥ÀÌÅÍ¿¡¼­´Â Á¤È®ÇÑ °ªÀÌ ³ª¿ÀÁö ¾ÊÀ» ¼ö ÀÖÀ»°Å °°½À´Ï´Ù.
 
 

Total 662
¹øÈ£ Á¦   ¸ñ ±Û¾´ÀÌ ³¯Â¥ Á¶È¸
582 Á¤º¸¿Ã¸²ÇǾƵå 2011 Áß.°íµîºÎ¿¹¼± ±âÃâ¹®Á¦Ç®ÀÌ (1) ±èÁ¤Èñ 03-31 7606
581 °æ±âµµ º»¼± Ä¿Æ®¶óÀÎÀÌ ¾î´ÀÁ¤µµ µÇ´ÂÁö¿ä? (1) ¹éÁöÈÆ 06-12 7602
580 548: ¹Ýº¹Á¦¾î¹®2 - ÀÚ°¡Áø´Ü8 (1) ¹ÚÁø 01-07 7581
579 µ¿¿µ»ó Àç»ý ´äº¯Á» ÇØÁÖ¼¼¿ä »çÁø ¿Ã·Á³ù½À´Ï´Ù ±èÁؼ­ 04-21 7491
578 ÇѱÛ2010 ¹«·á°­ÁÂ.... (1) Á¶¿µÈñ 02-27 7399
577 2012³âµµ ÃʵîºÎ 7¹ø (2) ±è½Ã¿ø 01-05 7391
576 ÀÚ±âÁÖµµc¾ð¾îÇÁ·Î±×·¡¹Ö ebook ±¸ÀÔ (1) ±èº´¼± 07-05 7378
575 Áú¹®µå¸³´Ï´Ù. (1) ÃÖÁ¤¹« 05-17 7369
574 ÃʵîÇлý,ÁßÇлý, °íµîÇлý ÆÐÅ°Áö·Î ±¸ºÐÇØÁÖ¸é ÁÁ°Ú¾î¿ä^^ (1) ±èÁø¿µ 05-06 7299
573 ¹®Á¦ Áú¹® (1) ¹éµµ¿ø 08-02 7281
572 Áú¹®µå¸³´Ï´Ù. (1) ÃÖÁ¤¹« 06-06 7243
571 ÀÚ±âÁÖµµ C¾ð¾î ÇÁ·Î±×·¡¹Ö °øµ¿±¸¸Å À̺¥Æ® °áÁ¦ (2) ÀÌ¿©Áø 04-26 7237
570 °­ÀǽÅûÇß½À´Ï´Ù. (1) ÀÌÁؼ® 02-02 7230
569 Á¤º¸¿Ã¸²ÇǾƵå 2012³â ¼Ò½ºÆÄÀÏÀº ¾ø³ª¿ä? (1) ÃÖ¿ø¹Ì 06-14 7212
568 ÀÌ°Å ÂÍ À߸øµÈ°Í °°Àºµ¥¿ä (1) ÀÌ´ë¿­ 01-20 7181
567 µ¿¿µ»ó Àç»ýÀÌ ¾ÈµË´Ï´Ù. (1) ÀåÇö¿µ 03-05 7154
566 2014³â Á¤¿Ã ¿¹¼±¹®Á¦ Áß°íµîºÎ ¹®Á¦ 28¹ø...¹®ÀÇ (1) À̹ÌÈ­ 03-20 7133
565 ÇÔ¼ö1 Çü¼ºÆò°¡ 5 (1) ½ÅÁ¾Çö 02-25 7127
564 2010³â Áß°íµîºÎ¿¹¼± 29¹ø¹®Á¦ ¿À·ù (1) ¹éÁöÈÆ 04-05 7105
563 ¹®Á¦ÄÚµå 1658, ¹®Á¦ÄÚµå 2571 ÀÓ¿¹Âù 04-24 7098
 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30    

ȸ»ç¼Ò°³ | °³ÀÎÁ¤º¸Ã³¸®¹æħ | ÀÌ¿ë¾à°ü | ã¾Æ¿À½Ã´Â ±æ | À̸ÞÀÏÁÖ¼Ò ¹«´Ü¼öÁý°ÅºÎ | »ç¾÷ÀÚÁ¤º¸È®ÀÎ
°æ±âµµ ¾È¾ç½Ã µ¿¾È±¸ È£°èµ¿ 1065-10 Çù¼º°ñµåÇÁ¶óÀÚ 601È£ ÇÑÄÄ¿¡µàÄÉÀ̼Ç(ÁÖ) TEL : 031-388-8840 FAX : 031-388-0996
´ëÇ¥ÀÚ : ±èµ¿±Ô »ç¾÷ÀÚ¹øÈ£ : 130-86-02870 Åë½ÅÆǸž÷½Å°í¹øÈ£ : Á¦ 2010-°æ±â¾È¾ç-888È£
COPYTIGHT(C) ÇÑÄÄ¿¡µàÄÉÀ̼Ç(ÁÖ), ALL RIGHT RESERVED.
´ãÀº°­Á : 0