NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2014國中組初賽
 NPSC-2014國中組初賽 D. 貓熊羽哲

作者 主題: NPSC-2014國中組初賽 D. 貓熊羽哲  (閱讀 849 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
NPSC-2014國中組初賽 D. 貓熊羽哲
« 於: 十一月 26, 2014, 12:13:59 am »

只有三步,各種方向 加轉90度只有15種,就不用寫旋轉,直接建表 {0右、1下、2左}

  [ 0] 、[1]、[2]、[3]、 [4]、[5]、[6]、 [7]、[8]、[9]、[10]、[11]、 [12]、[13]、[14]
  000、001、010、011、012、100、101、110、111、112、121、122、211、212、221
 
對每1格,各走以上15種,找最大值   {150x50x50x15x4應該不會逾時吧}
代碼: [選擇]
/*
NPSC 2014 國中組初賽 D.貓熊羽哲

*/

#include <cstdio>
//#include <iostream>
// using namespace std;
int a[50][50];
int mr[]={0 , 1, 0}; // 右、下、左
int mc[]={1 , 0,-1};

int b[15][3] = { {0,0,0}, {0,0,1}, {0,1,0}, {0,1,1}, {0,1,2} ,
{1,0,0}, {1,0,1}, {1,1,0}, {1,1,1}, {1,1,2} ,
{1,2,1}, {1,2,2}, {2,1,1}, {2,1,2}, {2,2,1} };
int main()
{
  int i,j,k,t,n,m ,ans;
  int r,c,d,sum;
  scanf("%d",&t);
    while( t-- )
    {
  scanf("%d %d",&n,&m);
      for(i=0; i<n; ++i)
      for(j=0; j<m; ++j)
scanf("%d", &a[i][j]);
ans = 0;
      for(i=0; i<n; ++i)
      {
      for(j=0; j<m; ++j)
      {
for(k=0;k<14;++k)
{
r=i; c=j;
sum=a[r][c];
d=0;
for(d=0; d<3; ++d)
{
r += mr[b[k][d]];  c += mc[b[k][d]];
if( r>=n || c<0 || c>=m) break;
sum += a[r][c];
}
if(sum>ans) ans=sum;
} // k
      } // j
      } // i
      printf("%d\n",ans);
   }
  return 0;
}
/*
3
3 4
6 1 1 1
9 5 1 1
2 2 7 1
5 5
8 8 1 1 1
1 8 8 1 1
1 1 2 1 1
2 3 1 7 7
5 4 1 9 7
10 10
706 534 580 290 302 775 15  761 815  710
46  415 863 791 374 962 872 57  950  365
525 768 54  593 469 299 623 648 264  280
830 825 590 987 911 227 696 981 244  534
107 1000 677 16 576 101 104 799 285  46
296 383 301 949 980 402 279 161 163  647
411 413 713 327 634 208 187 584 81   458
906 262 786 379 290 920 632 628 429  9998
562 695 914 835 23  544 917 431 678  2503
514 463 354 405 270 56  244 980 9161 391

------------
23
32
22340
*/

« 上次編輯: 十一月 26, 2014, 12:17:23 am 由 rscpp »
記錄

w80707

  • 新手
  • *
  • 文章數: 2
    • 檢視個人資料
Re: NPSC-2014國中組初賽 D. 貓熊羽哲
« 回覆 #1 於: 十一月 22, 2015, 11:34:24 am »

第31行WA了
for(k=0;k<14;++k)應該是for(k=0;k<15;k++)
要不然會少一種走法
« 上次編輯: 十一月 23, 2015, 07:44:15 pm 由 w80707 »
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2014國中組初賽
 NPSC-2014國中組初賽 D. 貓熊羽哲