hdu 1428 좋 은 제목 기억 화 검색 + 광 수 디 제 스 트 라 실현
3033 단어 알고리즘 - 검색
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4369 Accepted Submission(s): 1355
Problem Description
LL 은 최근 AC 에 빠 져 매일 침실, 기관실 두 시 일 선 에 빠 져 있다.오랫동안 컴퓨터 옆 에 앉 아 있 었 기 때문에 운동 이 부족 하 다.그 는 매번 침실 에서 기관실 까지 의 시간 을 충분히 이용 해 캠퍼스 를 산책 하기 로 했다.전체 HDU 캠퍼스 는 사각형 구 조 를 가지 고 n * n 개의 작은 사각형 으로 나 눌 수 있 으 며 각 지역 을 대표 합 니 다.예 를 들 어 LL 이 거주 하 는 18 호 기숙 사 는 캠퍼스 의 서북쪽, 즉 방 격 (1, 1) 이 대표 하 는 곳 에 위치 하고 기관실 이 있 는 세 번 째 실험 건물 은 동남쪽 끝 (n, n) 에 있다.LL 은 여러 코스 를 선택 할 수 있 기 때문에 매번 산책 코스 가 다 르 기 를 바란다.또한 그 는 A 구역 에서 B 구역 까지 B 에서 기관실 까지 의 노선 이 그 어떠한 A 에서 기관실 까지 의 노선 보다 더 가깝다 는 것 을 고려 했다. (그렇지 않 으 면 영원히 기관실 에 도착 하지 못 할 수도 있다.)지금 그 가 알 고 싶 은 것 은 모든 요 구 를 만족 시 키 는 노선 이 모두 몇 개 인지 이다.당신 은 그 에 게 알려 줄 수 있 습 니까?
Input
각 그룹 테스트 데이터 의 첫 번 째 행동 n (2 =
Output
각 조 의 테스트 데 이 터 를 대상 으로 총 노선 수 (2 ^ 63 보다 작 음) 를 출력 합 니 다.
Sample Input
3 1 2 3 1 2 3 1 2 3 3 1 1 1 1 1 1 1 1 1
Sample Output
16
代码：
/* ， a b b b a ， n，n ， ， */ #include#include #include using namespace std; #define MAX 55 #define INF 999999999 struct node { int x,y; }; int n; int map[MAX][MAX]; int dis[MAX][MAX]; long long int dp[MAX][MAX]; int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; bool jude(int x,int y) { if(x<1||x>n||y<1||y>n) return false; return true; } void BFS()//bfs { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) dis[i][j]=INF; } queue q; node next={n,n}; q.push(next); dis[n][n]=map[n][n]; while(!q.empty()) { node a=q.front(); q.pop(); for(int i=0;i<4;i++) { int xx=a.x+dir[i][0]; int yy=a.y+dir[i][1]; if(!jude(xx,yy)) continue; if(dis[xx][yy]>dis[a.x][a.y]+map[xx][yy]) { dis[xx][yy]=dis[a.x][a.y]+map[xx][yy];// ， 。 node nexttt={xx,yy}; q.push(nexttt); } } } } long long int dfs(int x,int y)// ； { if(dp[x][y]!=-1) return dp[x][y]; long long int count=0; for(int i=0;i<4;i++) { int xx=x+dir[i][0]; int yy=y+dir[i][1]; if(!jude(xx,yy)) continue; if(dis[xx][yy]
좋은 웹페이지 즐겨찾기
