fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. char chess[1200][1200];
  4. int dx[] = {-2,-1,1,2};
  5. int dy[] = {1,2,2,1};
  6.  
  7. int dp[1200][1200];
  8. bool visited[1200][1200];
  9. int h;
  10. int dfs(int i,int j)
  11. {
  12.     if(dp[i][j]!=-1)
  13.     return dp[i][j];
  14.  
  15.     if(j==h-1)
  16.     return 0;
  17.  
  18.     //visited[i][j]=1;
  19.     dp[i][j]=0;
  20.     for(int k=0;k<4;k++)
  21.     {
  22.         int nx = i + dx[k];
  23.         int ny = j + dy[k];
  24.         if(nx>=0&&ny>=0&&nx<h&&ny<h)
  25.         {
  26.             //if(!visited[nx][ny])
  27.             //{
  28.                 visited[nx][ny]=1;
  29.                 int r = 0;
  30.                 if(chess[nx][ny]=='P')
  31.                 r=1;
  32.                 dp[i][j] = max(dp[i][j],r+dfs(nx,ny));
  33.         //    }
  34.         }
  35.     }
  36.  
  37.     return dp[i][j];
  38. }
  39. int main()
  40. {
  41.     int t;
  42.     scanf("%d",&t);
  43.     while(t--)
  44.     {
  45.         scanf("%d",&h);
  46.  
  47.         for(int i=0;i<h;i++)
  48.         cin>>chess[i];
  49.  
  50.         int k_x,k_y;
  51.         for(int i=0;i<h;i++)
  52.         {
  53.             for(int j=0;j<h;j++)
  54.             {
  55.                 if(chess[i][j]=='K')
  56.                 {
  57.                     k_x = i;
  58.                     k_y =j;
  59.                     break;
  60.                 }
  61.  
  62.             }
  63.         }
  64.  
  65.  
  66.         for(int i=0;i<h;i++)
  67.         for(int j=0;j<h;j++)
  68.         dp[i][j]=-1;
  69.         cout<<dfs(k_x,k_y)<<"\n";
  70.  
  71.     }
  72.  
  73.  
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0s 11736KB
comments (?)
stdin
copy 
1
5
K....
..P..
.P...
...P.
.....
stdout
copy 
2
https://ideone.com/jHk7eg
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!