코딩의노예

#include <cstdio>
#include <cstdlib>
#include <cstring>

#define N 200
#define BLACK 'b'
#define WHITE 'w'

char table[N+1][N+1];
int visit[N+1][N+1];
int n,numLine;

int dfs(int row, int col)
{
 int result=0;
 //끝노드에 도달할경우 1을 리턴
 if(row == numLine){
  return 1;
 }
 //움직일 수 있는 곳이 있으면 해당 노드를 방문
 if(!visit[row-1][col-1]&&table[row-1][col-1]==BLACK){
  visit[row-1][col-1]=1;
  result += dfs(row-1,col-1);
 }if(!visit[row-1][col]&&table[row-1][col]==BLACK){
  visit[row-1][col]=1;
  result += dfs(row-1,col);
 }if(!visit[row][col-1]&&table[row][col-1]==BLACK){
  visit[row][col-1]=1;
  result += dfs(row,col-1);
 }if(!visit[row][col+1]&&table[row][col+1]==BLACK){
  visit[row][col+1]=1;
  result += dfs(row,col+1);
 }if(!visit[row+1][col]&&table[row+1][col]==BLACK){
  visit[row+1][col]=1;
  result += dfs(row+1,col);
 }if(!visit[row+1][col+1]&&table[row+1][col+1]==BLACK){
  visit[row+1][col+1]=1;
  result += dfs(row+1,col+1);
 }
 return result;
}
int solve()
{
 int num;
 //Black으로 체크
 for(int i=1; i<=numLine; i++){
  if(table[1][i] == BLACK){
   memset(visit,0,sizeof(int)*(N+1)*(N+1));
   if(num=dfs(1,i)){
    return 1;
   }
  }
 }
 return 0;
}
int main(){
 int num=1;
 while(scanf("%d",&numLine)&&numLine){
  for(int i=1; i<=numLine;i++){
   scanf("%s",table[i]+1);
  }
  solve() ? printf("%d B\n",num) : printf("%d W\n",num);
  num++;
 }
 return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>

#define LEN 20
#define ALPHABET 26
#define MAX 9000
#define alpha(a) ( (a) - 'A')
#define isAlpha(a) ( (a) >= 'A' && (a) <='Z' ? 1 : 0 )

using namespace std;

typedef struct Vertex{
 int idx;
 int depth;
};

char input[LEN+1];
char graph[ALPHABET+1][ALPHABET+1];
char data[MAX][LEN+1];
int visit[ALPHABET+1];
int cnt;
Vertex vertex[ALPHABET+1];
int v[ALPHABET+1];

int dfs(int v)
{
 int depth=1,i;
 for(i=0; i < ALPHABET; i++){
  if(!visit[i] && graph[v][i]){
   visit[i]=1;
   depth += dfs(i);
  }
 }
 return depth;
}
bool comp(Vertex a, Vertex b){
 if(a.depth > b.depth)
  return true;
 else
  return false;
}
void solve()
{
 int pos = -1,i,j=1;
 for( i = 0; i < LEN; i++){
  pos = 0;j=1;
  for(pos=0; pos<cnt; pos++){
   if( (isAlpha(data[pos][i]) && isAlpha(data[j][i])) &&
    alpha(data[pos][i]) != alpha(data[j][i])){
     //
     if(i==0 ||  (strncmp(data[j],data[pos],i)==0)){

      graph[alpha(data[pos][i])][alpha(data[j][i])] = 1;
      
      if(v[alpha(data[pos][i])]==0)
       v[alpha(data[pos][i])]=1;
      
      if(v[alpha(data[j][i])]==0)
       v[alpha(data[j][i])]=1;
     }
   }j++;
  }
 }
 for( i = 0; i < ALPHABET; i++){
  if(v[i]){
   memset(visit,0,sizeof(int)*(ALPHABET+1));
   vertex[i].depth = dfs(i);
  }
 }
 sort(&vertex[0],&vertex[ALPHABET],comp);
 for(int i=0; i<ALPHABET; i++){
  if(vertex[i].depth>0){
   printf("%c",vertex[i].idx+'A');
  }
 }printf("\n");
}
int main()
{
 for(int i=0; i<ALPHABET; i++){
  vertex[i].depth = -1;
  vertex[i].idx = i;
 }
 while(scanf("%s",data[cnt])&&data[cnt][0] != '#'){
  cnt++;
 }
 solve();
 return 0;
}

#include <cstdio>
#include <cstring>
#include <cstdlib>

#define INPUT_MAX 100000+1
#define QUERY_MAX 1000+1
#define ALPHABET 26
#define min(a,b) (a) > (b) ? (b) : (a)

char input[INPUT_MAX+1];
char query[QUERY_MAX+1];
char func[QUERY_MAX+1+1][ALPHABET*2];
char alphabet[ALPHABET*2];
char suffix[QUERY_MAX];

int testCase,numQuery,numState,acceptState;
int lenInput;

void init(){
 for(int i=0; i < ALPHABET; i++){
  alphabet[i]='a'+i;
  alphabet[i+ALPHABET]='A'+i;
 }
}
int solve(){
 int q = 0;
 
 for(int i=0; i < lenInput; i++){
  q = func[q][ input[i]-'a' < 0 ? input[i]-'A':input[i]-'a' ];
  if(q==acceptState)
   return 1;
 }
 return 0;
}
void makeTransitionFunc(){
 int k,temp;
 for(int i=0; i <=numState; i++){
  suffix[i]=query[i];
  for(int j=0 ;j <ALPHABET*2;j++){
   k = min(numState-1,i);
   //suffix check - 꼬리부분
   //prefix가 query의 suffix에 일치하는지 확인해야댐
   //p[0...k]를 p[0...a]끝에 붙여서 확인했을때에
   temp=query[i];
   query[i]=alphabet[j];
   while( strncmp(suffix,query+i-k,k+1) ){
    k--;
   }
   query[i]=temp;
   //상태는 query의 index를 의미한다
   //해당 상태에 어떤 알파벳이 나올경우 k+1이라는 상태로 전이함
   if(k==-1)
    func[i][j]=0;
   else
    func[i][j] = k+1;
  }
 }
}

int main(){
 init();
 scanf("%d",&testCase);
 
 while(testCase-->0){
  scanf("%s",input);
  lenInput = strlen(input);
  scanf("%d",&numQuery);
  
  while(numQuery-->0){
   scanf("%s",query);
   numState = strlen(query);
   acceptState = numState;
   makeTransitionFunc();
   if(solve())
    printf("y\n");
   else
    printf("n\n");
  }
 }
 return 0;
}

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define NUM 100
#define GAS 200
#define MAX 40000000

typedef struct {
 short distance;
 short cost;
}station;

station r[NUM+1];

int dp[NUM+1][GAS+1];
int input;
char buf[255];

int main(){

 int i,j,k,l;
 int min=MAX,delta;
 int liter=0;
 int testCase,num=0;
 
 gets(buf);
 sscanf(buf,"%d",&testCase);
 gets(buf);
 
 while(testCase--){
  
  gets(buf);
  sscanf(buf,"%d",&input);
  num=0; memset(dp,0,sizeof(int)*(NUM+1)*(GAS+1));
  memset(r,0,sizeof(station)*(NUM+1));
 
  while(gets(buf)!=NULL){
   if(buf[0]=='\0')
    break;
   ++num;
   sscanf(buf,"%d %d",&r[num].distance,&r[num].cost);
   if(r[num].distance < 0 ||  r[num].distance > input) num--;
  }
 
  for(i=0; i <=num; i++){
   for(j=0; j<=GAS; j++){
    dp[i][j] = MAX;
   }
  }
  //아무곳도 안가고 가스가 100남았으므로 비용은 0원
  dp[0][100] = 0;
  //처음 가스 100으로 방문할 수 있는 주유소 설정
  for(i=1; i <=num; i++){
   //해당 주유소까지 갔을때에 남은 가스의 양
   delta = 100 - r[i].distance;
   //앞으로 방문할 수 없으므로 그냥 반복문 종료시킴
   if(delta < 0)
     break;
   for(j=0; j<=GAS; j++){
    //해당 주유소에서 보유가스가 해당 주유소까지 갔을떄 남은 가스의 양이면
    //드는 비용은 0원
    if(delta == j)
    {
     dp[i][j] = 0;
    }
    //해당 주유소에 도착했을때에 j만큼 가스가 있을때에 드는 충전비용
    if(delta < j)
    {
     dp[i][j] = (j-delta)*r[i].cost;
    }
   }
  }
  for( i = 1; i <= num; i++){
   for(j=0; j <= GAS; j++){
    for(k = 1; k <= i-1; k++){
     delta = r[i].distance - r[k].distance;
     if(delta > GAS)
      continue;
     
     for(l=delta; l <= delta+j && l <= GAS; l++){
      //해당 주유소에서 다음 가야할 주유소까지 보유할 가스만큼 다 채워놓음
      if(l + j < GAS && dp[k][l]+r[k].cost*(j-l+delta) < dp[i][j]){
       dp[i][j]=dp[k][l]+r[k].cost*(j-l+delta);
      }
      //해당 주유소에서 다음 가야할 주유소까지 최소의 가스를 채워놓고
      //도착 주유소에서 나머지 가스를 채워놓음
      if( dp[k][l]+r[i].cost*(delta+j-l) < dp[i][j]){
       dp[i][j]=dp[k][l]+r[i].cost*(delta+j-l);
      }
     }
   
    }
   }
  }
  min=MAX;
  for(i = 0; i<=num; i++){
   delta= input - r[i].distance;
   if(delta > GAS || delta < 0)
     continue;
   for(j=0; j<=GAS; j++){
    if((r[i].distance + j) == input){
     if(j+100 <= GAS && dp[i][j+100] < min){
      min = dp[i][j+100];
     }
    }
   }
  }
  if(min == MAX)
   printf("Impossible\n");
  else
   printf("%d\n",min);
  if(testCase)
   putchar('\n');
  
 }

 return 0;
}

#include <cstdio>

#define SIZE 100

int dp[SIZE+2][SIZE+2];
int input[SIZE+1][SIZE+1];
int max = -0x80000000;

int numCase;

int main()
{
 int cnt=0,i=0,j=0,k=0,l=0,sum=0;
 scanf("%d",&numCase);
 for(i =0 ; i < numCase; i++){
  for( j = 0; j < numCase; j++){
   scanf("%d",&input[i][j]);
  }
 }
 dp[1][1] = input[0][0];

 for(i=2; i <= numCase; i++){
  dp[i][1] += dp[i-1][1] + input[i-1][0]; 
  dp[1][i] += dp[1][i-1] + input[0][i-1];
 }
 for(i=2; i <= numCase; i++){
  for(j=2; j <= numCase; j++){
   dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + input[i-1][j-1];
  }
 }
 for(i=0; i < numCase; i++){
  for(j=i+1; j<=numCase; j++){
   for(k=0; k < numCase; k++){
    for(l=k+1; l<=numCase; l++){
     sum = dp[j][l] - dp[i][l] - dp[j][k] + dp[i][k];
     if(sum > max){
      max = sum;
     }
    }
   }
  }
 }
 printf("%d\n",max);
 return 0;
}