wxzwsj197950 wxzwsj197950
关注数: 17 粉丝数: 146 发帖数: 1,396 关注贴吧数: 47
一道算法题求助(英文) Game Jeff loves playing games, Gluttonous snake( an old game in NOKIA era ) is one of his favourites. However, after playing gluttonous snake so many times, he finally got bored with the original rules. In order to bring new challenge to this old game, Jeff introduced new rules : The ground is a grid, with n rows and m columns(1 <= n, m <= 500). Each cell contains a value v (-1≤vi≤ 99999), if v is -1, then this cell is blocked, and the snake can not go through, otherwise, after the snake visited this cell, you can get v point. The snake can start from any cell along the left border of this ground and travel until it finally stops at one cell in the right border. During this trip, the snake can only go up/down/right, and can visit each cell only once. Special cases : a. Even in the left border and right border, the snake can go up and down b. When the snake is at the top cell of one column, it can still go up, which demands the player to pay all current points , then the snake will be teleported to the bottom cell of this column and vice versa. After creating such a new game, Jeff is confused how to get the highest score. Please help him to write a program to solve this problem. Input The first line contains two integers n (rows) andm (columns), (1 <= n, m <= 500), separated by a single space. Next n lines describe the grid. Each line contains m integers vi (-1≤vi≤99999) vi = -1 means the cell is blocked. Output Output the highest score you can get. If the snake can not reach the right side, output -1. 下面是我写的代码用暴力的dfs搜索,但是运行是错的,不知道为什么,求大神帮忙看看哪错了,新手求助 #include <iostream> #include <fstream> using namespace std; int m,n; int map[505][505]; bool isVisited[505][505]; int max=0; void dfs(int h,int l,int sum) { if(l>=m) { if(sum>max) { max = sum; } cout<<sum<<endl; return; } if(h<0) dfs(n-1,l,0); if(h>=n) dfs(0,l,0); if(map[h][l]==-1) return; if(isVisited[h][l]) return; isVisited[h][l] = true; dfs(h,l+1,sum+map[h][l]); dfs(h-1,l,sum+map[h][l]); dfs(h+1,l,sum+map[h][l]); } int main() { ifstream cin("F:\\data.in"); cin>>n>>m; int i,j; for(i=0;i<n;i++) for(j=0;j<m;j++) { cin>>map[i][j]; isVisited[i][j]=false; } for(i=0;i<n;i++) { dfs(i,0,0); } return 0; }
菜鸟又来求大神帮忙,看一下这个五子棋判断胜负不起作用 #include<stdio.h> #include<graphics.h> #include<stdlib.h> #include<conio.h> int p1_qipan[20][20]={0}; int p2_qipan[20][20]={0}; int player=1; void hua_qi_pan(void) { initgraph(400,400); int x=40,y=0; while(x<=400) { line(x,y,x,400); x+=40; } x=0;y=40; while(y<=400) { line(x,y,400,y); y+=40; } } int judgeWin(int qi_pan[20][20]); void GameOver(int winPlay) { if(winPlay==1) outtextxy(150,200,"玩家一获胜"); if(winPlay==2) outtextxy(150,200,"玩家二获胜"); getch(); } int main(void) { hua_qi_pan(); while(1) { while(player==1) { setfillstyle(RED); MOUSEMSG m; m=GetMouseMsg(); if(m.mkLButton==true) { if(m.x%40!=0||m.y%40!=0) { if(m.x%40<=20) { m.x=m.x-m.x%40; } if(m.y%40<=20) { m.y=m.y-m.y%40; } if(m.x%40>20) { m.x=m.x-m.x%40+40; } if(m.y%40>20) { m.y=m.y-m.y%40+40; } } if(p2_qipan[m.x/20][m.y/20]==0) { fillcircle(m.x,m.y,18); p1_qipan[m.x/20][m.y/20]=1; player=2; } } } if(judgeWin(p1_qipan)) { GameOver(1); } ////////////////////////////////////////////////////////////////// while(player==2) { setfillstyle(BLUE); MOUSEMSG m; m=GetMouseMsg(); if(m.mkLButton==true) { if(m.x%40!=0||m.y%40!=0) { if(m.x%40<=20) { m.x=m.x-m.x%40; } if(m.y%40<=20) { m.y=m.y-m.y%40; } if(m.x%40>20) { m.x=m.x-m.x%40+40; } if(m.y%40>20) { m.y=m.y-m.y%40+40; } } if(p1_qipan[m.x/20][m.y/20]==0) { fillcircle(m.x,m.y,18); p2_qipan[m.x/20][m.y/20]=1; player=1; } } } if(judgeWin(p2_qipan)) { GameOver(2); } ///////////////////////////////////////////////////////////// } return 0; } int judgeWin(int qi_pan[20][20]) { for(int x=0;x<=15;x++) for(int y=0;y<=15;y++) { if(qi_pan[x][y]==1 && qi_pan[x+1][y]==1 && qi_pan[x+2][y]==1 && qi_pan[x+3][y]==1 && qi_pan[x+4][y]==1) return 1; if(qi_pan[x][y]==1 && qi_pan[x][y+1]==1 && qi_pan[x][y+2]==1 && qi_pan[x][y+3]==1 && qi_pan[x][y+4]==1) return 1; if(qi_pan[x][y]==1 && qi_pan[x+1][y+1]==1 && qi_pan[x+2][y+2]==1 && qi_pan[x+3][y+3]==1 && qi_pan[x+4][y+4]==1) return 1; } return 0; }
1 下一页