poj-2488 a knight's journey(搜索題)

来源:https://www.cnblogs.com/smallhester/archive/2018/08/18/9499143.html
-Advertisement-
Play Games

Time limit1000 ms Memory limit65536 kB Background The knight is getting bored of seeing the same black and white squares again and again and has decid ...


Time limit1000 ms

Memory limit65536 kB

 

Background 
The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey 
around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans? 

Problem 
Find a path such that the knight visits every square once. The knight can start and end on any square of the board.

Input

The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .

Output

The output for every scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number. 
If no such path exist, you should output impossible on a single line.

Sample Input

3
1 1
2 3
4 3

Sample Output

Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4


題意:騎士走棋盤,要求把所有的各自都要走一遍,並且要輸出走棋盤的格子
題解:dfs搜索吧,註意每次可以搜索的時候都要把步數加一,當步數等於格子數時就可以了
#include<iostream>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
#define PI 3.14159265358979323846264338327950


int path[100][2],vis[100][100],p,q,cnt;
bool flag;
int dx[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
int dy[8] = {-2, -2, -1, -1, 1, 1, 2, 2};

bool judge(int x,int y)
{
    if(x<=p && x>=1 && y<=q && y>=1 && !vis[x][y] )
        return true;
    return false;
}
void dfs(int r,int c,int step)
{
    if (flag == false)
    {
        path[step][0]=r;
        path[step][1]=c;
    }
        if(step==p*q)
    {
        flag=true;
        return ;
    }
    for(int i=0;i<8;i++)
    {
        int nx=r+dx[i];
        int ny=c+dy[i];
        if(judge(nx,ny))
        {
            vis[nx][ny]=1;
            dfs(nx,ny,step+1);
            vis[nx][ny]=0;
        }
    }
}
int main()
{
    int i,t,cas=0;
    cin>>t;
    while(t--)
    {
        flag=0;
        cin>>p>>q;
        memset(vis,0,sizeof(vis));
        vis[1][1]=1;
        dfs(1,1,1);
        printf("Scenario #%d:\n",++cas);
        if(flag)
        {
            for(i=1;i<=p*q;i++)
            {
                printf("%c%d",path[i][1]-1+'A',path[i][0]);
            }
        }
        else
            printf("impossible");
        printf("\n");
        if(t!=0)
            printf("\n");
    }
}

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 靜態語言 在編寫代碼時,必須為變數指定一個明確類型的語言。比如Java、C/C++ 動態語言 在編寫代碼時,不必為變數指定一個明確的類型,而是由解釋器在運行時根據變數的使用情況確定變數的類型。比如python、javascript 強類型語言 變數必須有一個確定的類型。比如Java、C/C++、py ...
  •   Python一切皆對象(object),每個對象都可能有多個屬性(attribute)。Python的屬性有一套統一的管理方案。   屬性的__dict__系統 對象的屬性可能來自於其類定義,叫做類屬性(class attribute)。類屬性可能來自類定義自身,也可能根據類 ...
  • 一、大概思路 1、從cookie中取商品列表 2、判斷要添加的商品是否存在cookie中。 3、如果已添加過,則把對應的商品取出來,把要添加的商品的數量加上去。 4、如果沒有添加過,則把改商品添加到商品列表中。 5、再把商品列表序列化,加入cookie中。 二、代碼實現 1、定義一個購物車商品的po ...
  •   Python一切皆對象,但同時,Python還是一個多範式語言(multi paradigm),你不僅可以使用面向對象的方式來編寫程式,還可以用面向過程的方式來編寫相同功能的程式(還有函數式、聲明式等,我們暫不深入)。Python的多範式依賴於Python對象中的特殊方法(specia ...
  • 異常處理 在項目開發中,異常處理是不可或缺的。異常處理幫助人們debug,通過更加豐富的信息,讓人們更容易找到bug的所在。異常處理還可以提高程式的容錯性。 我們之前在講迴圈對象的時候,曾提到一個StopIteration的異常,該異常是在迴圈對象窮盡所有元素時的報錯。 我們以它為例,來說明基本的異 ...
  • Time limit1000 ms Memory limit65536 kB The multiplication puzzle is played with a row of cards, each containing a single positive integer. During the ...
  • 1.ValueOf和強轉的區別? Case1: 需要強調的是String.valueOf()方法,當參數為類型是object,且值時null的時候他的處理方式 Case2: 基本包裝類型(Long,Integer等)的valueOf(Object)的處理和String不一樣,Object是null就 ...
  • 為什麼我們編寫的程式可以運行在電腦上?我們編寫的程式會經過編譯,翻譯成為電腦可以運行的電腦指令。 電腦語言是我們頭腦的延伸,就像音樂,繪畫和電影一樣,創造一種具有表達的藝術的東西。 面向對象程式設計就像自然界中的物種學家分類物種一樣,他們具有某些共同的特征,所以我們通過class類的概念,我 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...