1002 Fire Net，1002firenet

1002 Fire Net，1002firenet

用遞歸實現各種情況的枚舉，可以看做是考察DPS的簡單實現。

 1 #include <stdio.h>
 2 
 3 int n,max,count,target[4][4];
 4 
 5 int place(int x,int y){
 6     int i;
 7     for(i=y;i>=0;i--){
 8         if(target[x][i]>0)
 9             return 0;
10         if(target[x][i]<0)
11             break;
12     }
13     for(i=y;i<n;i++){
14         if(target[x][i]>0)
15             return 0;
16         if(target[x][i]<0)
17             break;
18     }
19     for(i=x;i>=0;i--){
20         if(target[i][y]>0)
21             return 0;
22         if(target[i][y]<0)
23             break;
24     }
25     for(i=x;i<n;i++){
26         if(target[i][y]>0)
27             return 0;
28         if(target[i][y]<0)
29             break;
30     }
31     return 1;
32 }
33 
34 void DFS(){
35     int i,j;
36     if(count>max)
37         max=count;
38     for(i=0;i<n;i++){
39         for(j=0;j<n;j++){
40             if(!target[i][j]&&place(i,j)){
41                 target[i][j]=1;
42                 count++;
43                 DFS();
44                 count--;
45                 target[i][j]=0;
46             }
47         }
48     }
49 }
50 
51 int main(){
52     int i,j;
53     char c;
54     while(1){
55         scanf("%d",&n);
56         if(n==0)
57             break;
58         max=count=0;
59         for(i=0;i<n;i++){
60             getchar();
61             for(j=0;j<n;j++){
62                 scanf("%c",&c);
63                 target[i][j]=(c=='X'?-1:0);
64             }
65         }
66         DFS();
67         printf("%d\n",max);
68     }
69     return 0;
70 }

ACM的OJ題1002： fire net助 本地測試都正確，但提交總是出錯

之前A過的，給你參考參考
#include<iostream>
#include<cstring>
using namespace std;

char map[4][4];
int maxt;

bool legal(int a,int b)
{
int i;
if(map[a][b]=='X'||map[a][b]=='+')return false;
for(i=a-1;i>=0;i--)
{
if(map[i][b]=='+')return false;
else if(map[i][b]=='X')break;
}
for(i=b-1;i>=0;i--)
{
if(map[a][i]=='+')return false ;
else if(map[a][i]=='X')break;
}
return true;
}

void maker(int k,int count,int n)
{
int i,j;
if(k==n*n)
{
if(count>maxt)maxt=count;
return;
}
else
{
i=k/n;
j=k%n;
if(legal(i,j))
{
map[i][j]='+';
maker(k+1,count+1,n);
map[i][j]='.';
}
maker(k+1,count,n);
}
}

int main()
{
int n;
while(cin>>n)
{
if(n==0)break;
int i,j;
for(i=0;i<n;i++)for(j=0;j<n;j++)cin>>map[i][j];
maxt=0;
maker(0,0,n);
cout<<maxt<<endl;
}
}
 

zoj 1002 FIRE NET 疑問 我的思路有問題？

因為Windows的開發者自己定義了CHAR和TCHAR，他們自己定義的CHAR是unsigned char，為了防止不同編譯器產生不同的代碼，因為C標准並沒有規定說char必須是不是unsigned的。所以自己固定一種比較好。而且為了兼容DOS下對8位擴展ASCII碼處理，應該是0~255的范圍。-128~127的char只是早期C語言編譯器習慣的定義，這個定義微軟的C編譯器也繼承了，但是OS開發者和編譯器團隊都想要一些獨立性。