dp uva-825-Walking on the Safe Side
제목 링크:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=766
제목:
왼쪽 상단 에서 오른쪽 하단 으로 가 는 가장 짧 은 경로 가 몇 가지 인지 표를 주세요.그 중 몇몇 교차점 은 갈 수 없다.
문제 풀이 방향:
dp.
코드:
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#define eps 1e-6
#define INF (1<<20)
#define PI acos(-1.0)
using namespace std;
//
long long dp[2200][2200],m,n;
int save[2200][2200];
int dir[2][2]={{0,1},{1,0}}; // ,
bool issure(int row,int column) //
{
if(row<1||row>m||column<1||column>n)
return false;
return true;
}
long long dfs(int row,int column)
{
if(row==m&&column==n) //
return dp[m][n]=1;
if(dp[row][column]) // ,
return dp[row][column];
long long tempans=0;
for(int i=0;i<2;i++) //
{
int temprow=row+dir[i][0],tempcolumn=column+dir[i][1];
if(issure(temprow,tempcolumn)&&save[temprow][tempcolumn]==0)
tempans+=dfs(temprow,tempcolumn);
}
return dp[row][column]=tempans;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&m,&n);
memset(save,0,sizeof(save));
memset(dp,0,sizeof(dp));
//memset(visit,false,sizeof(visit));
for(int i=1;i<=m;i++)
{
int tempint;
char tempchar[220];
scanf("%d",&tempint);
gets(tempchar);
int len=strlen(tempchar);
int num=0;
for(int j=0;j<len;j++) //
{
if(isdigit(tempchar[j]))
num=num*10+tempchar[j]-'0';
else
{
save[i][num]=1;
num=0;
}
}
save[i][num]=1; // ,
/*scanf("%d%c",&tempint,&tempchar);
while(tempchar!='
') // ,
{
scanf("%d%c",&tempint,&tempchar);
save[i][tempint]=1;
}*/
}
if(save[1][1])
printf("0
");
else
printf("%lld
",dfs(1,1));
if(t)
putchar('
');
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.