9 도 OJ (1091) 보드게임
시간 제한: 1 초
메모리 제한: 32 메 가
특수 판정 문제: 아니오
제출: 622
해결: 155
제목 설명:
6 * 6 의 바둑판 이 있 습 니 다. 모든 바둑판 에 하나의 수치 가 있 습 니 다. 지금 은 또 하나의 시작 위치 와 종료 위치 가 있 습 니 다. 시작 위치 에서 종료 위치 까지 대가 가 가장 적은 경 로 를 찾 아 보 세 요. 1. 상하 좌우 네 방향 으로 만 이동 할 수 있 습 니 다. 2. 총 대 가 는 한 걸음 도 가지 않 은 대가 의 합 3. 한 걸음 (a, b 에서 c, d) 의 대 가 는 c, d 의 값 과 a 입 니 다.b 상의 상태의 곱 하기 4, 초기 상 태 는 1 이다.
한 걸음 걸 을 때마다 상 태 는 다음 과 같은 공식 에 따라 변화 한다. (이 걸음 의 대가% 4) + 1.
입력:
첫 줄 에 n 조 데이터 가 있 음 을 나타 내 는 정수 n 이 있 습 니 다. 각 조 의 데 이 터 는 처음에 6 * 6 의 행렬 이 었 고 행렬 의 값 은 1 보다 크 고 10 보다 작은 값 이 었 다. 그 다음 에 네 개의 정 수 는 시작 좌표 와 종료 좌 표를 나 타 냈 다.
출력:
수출 최소 대가.
샘플 입력:
11 1 1 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 1 1 11 1 1 1 1 10 0 5 5
샘플 출력:
23
이 문제 자체 가 어렵 지 않 습 니 다. 주로 이것 은 9 도 위 에 있 는 A 의 첫 번 째 4 성 문제 이기 때문에 share 를 꺼 내 보 세 요. 아주 간단 합 니 다. DFS 와 BFS 는 모두 할 수 있 습 니 다. 저 는 DFS 로 한 번 지 나 봤 습 니 다. 다음은 코드 입 니 다.
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <cstdlib>
using namespace std;
int sx,sy,ex,ey,ans;// ， ；
queue<int>q;
int dir[][2]={{-1,0},{1,0},{0,1},{0,-1}};
int visit[6][6];
int map[6][6];
void DFS(int x,int y,int sum,int statu)
{
if(sum<ans)
{
if(x==ex&&y==ey)
{
ans=sum;
return ;
}
for(int i=0;i<4;i++)
{
int nextx=x+dir[i][0];
int nexty=y+dir[i][1];
if(visit[nextx][nexty]&&nextx>=0&&nextx<6&&nexty>=0&&nexty<6)
{
int cost=statu*map[nextx][nexty];
visit[nextx][nexty]=0;
DFS(nextx,nexty,sum+cost,cost%4+1);
visit[nextx][nexty]=1;
}
}
}
}
int main()
{
int k;
cin>>k;
while(k--)
{
for(int i=0;i<6;i++)
{
for(int j=0;j<6;j++)
{
cin>>map[i][j];
visit[i][j]=1;
}
}
cin>>sx>>sy>>ex>>ey;
ans=1000000;
DFS(sx,sy,0,1);
cout<<ans<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
