POJ3050

文章目錄

• 前言
• 一、題目大意
• • 1.輸入
  • 2.輸出
• 二、解題思路
• 三、AC代碼
• 總結

前言

POJ題解這一系列文章主要記錄《挑戰程式設計程式設計》的課後習題，包括解題需要用到的知識，思路以及遇到的問題等等。

提示：以下是本篇文章正文内容，下面案例可供參考

一、題目大意

給定一個5*5大小的數字矩陣，從這個矩陣的任意一點出發，向前後左右四個方向移動（可以走回頭路），總共移動五次。将移動時經過數字連接配接成串（包括起點數字），計算總共能形成多少種不同的串（數字0可以放在任何地方）。

1.輸入

一個5*5的數字矩陣

2.輸出

移動五次能形成不同數字串的個數

二、解題思路

因為我們需要窮舉所有可能的移動方式，是以可以采用深度優先算法(DFS)來周遊所有可能的路徑。在統計不同數字串的數量時，我們可以将數字串先轉化為一個整數，再将其存放到set容器中。最後，列印set的尺寸即可。

set容器相關見: set容器及常見操作.

三、AC代碼

代碼如下（示例）：

#include<iostream>
#include<set>
using namespace std;
int grid[5][5];//5*5三個月左右
int dx[4]={-1,0,1,0};//x軸方向的移動
int dy[4]={0,-1,0,1};//y軸方向的移動
//x+dx[i],y+dy[i]用于控制上下左右的移動
int res = 0;
set<int> s;
void dfs(int x,int y,int sum,int step){//
	if(step==5){//當移動五步後，将生成的數字串加入到set中
		s.insert(sum);
		return;
	}
	for(int i=0;i<4;i++){
		int nx = x +dx[i];
		int ny = y +dy[i];
		if(nx>=0&&nx<5&&ny>=0&&ny<5){
			dfs(nx,ny,sum*10+grid[nx][ny],step+1);//sum*10+grid[x][y]用于将數字串轉化成數字
		}
	}
}

int main(){
	for(int i=0;i<5;i++){
		for(int j=0;j<5;j++){
			scanf("%d",&grid[i][j]);
		}
	}
	for(int x =0;x<5;x++){
		for(int y=0;y<5;y++){
			dfs(x,y,grid[x][y],0);//将5*5矩陣的每一個格子都進行DFS操作
		}
	}
	res=s.size();//s.size()就是不同數字串的數量
	printf("%d\n",res);
	}

           

總結

本文用深度優先算法配合set容器的方式來對POJ3050進行解答，窮舉了所有可能的排列，時間複雜度較高，但是較容易想到。